只支持整数间计算
思路 1.先将输入的中缀表达式转化为后缀表达式 ①初始化一个栈和一个List:运算符栈s和存储中间结果的容器L
②从左到右扫描输入的中缀表达式
③遇到 *** 作数时,将其add到容器L
④遇到运算符时,如下三种情况分类:
-
如果s为空;或栈顶运算符为左括号"(",则直接将此运算符入栈
-
否则,若该优先级高于栈顶运算符的,则直接将此运算符入栈
-
否则,若该优先级小于或等于栈顶运算符的,则将s栈顶的运算符d出add到L中,再在栈s中继续往下比较,(遇到比自己优先级大的就直接扔到L中)直到该运算符压入栈s为止
⑤遇到括号时:
-
如果是左括号"(",则直接压入栈s
-
如果是有括号")",则依次d出栈s栈顶的运算符,并add到容器L中,再在栈s中继续往下找,(遇到运算符就把其扔到容器L中)直到遇到左括号为止,并把左括号踢出栈(丢弃它)
⑥重复步骤②~⑤,直到将表达式遍历结束
⑦将栈s中剩余的运算符依次d出add到容器L中
⑧依次输出容器L的元素就是最终的后缀表达式
例题 输入的中缀表达式为"1+((2+3)*4)-5"的步骤
- 从左到右扫描得到的后缀表达式,
- 遇到数字就压入栈
- 遇到运算符d出栈顶的前两个数,计算,得到的结果又压回栈里
- 直到扫描完毕,栈中最后只留下一个数,即最终结果值
import java.util.ArrayList; import java.util.List; import java.util.Stack; public class PolandNotation { public static void main(String[] args) { //完成将一个中缀表达式转成后缀表达式的功能 //说明 //1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 – //2. 因为直接对str 进行 *** 作,不方便,因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List // 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] //3. 将得到的中缀表达式对应的List => 后缀表达式对应的List // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] String expression = "1+((2+3)*4)-5";//注意表达式 ListinfixexpressionList = toInfixexpressionList(expression); System.out.println("中缀表达式对应的List=" + infixexpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] List suffixExpreesionList = parseSuffixExpreesionList(infixexpressionList); System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ? } //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] //方法:将得到的中缀表达式对应的List => 后缀表达式对应的List public static List parseSuffixExpreesionList(List ls) { //定义两个栈 Stack s1 = new Stack (); // 符号栈 //说明:因为s2 这个栈,在整个转换过程中,没有pop *** 作,而且后面我们还需要逆序输出 //因此比较麻烦,这里我们就不用 Stack 直接使用 List s2 //Stack s2 = new Stack (); // 储存中间结果的栈s2 List s2 = new ArrayList (); // 储存中间结果的Lists2 //遍历ls for(String item: ls) { //如果是一个数,加入s2 if(item.matches("\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { //如果是右括号“)”,则依次d出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃 while(!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop();//!!! 将 ( d出 s1栈, 消除小括号 } else { //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符d出并加入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较 //问题:我们缺少一个比较优先级高低的方法 while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) { s2.add(s1.pop()); } //还需要将item压入栈 s1.push(item); } } //将s1中剩余的运算符依次d出并加入s2 while(s1.size() != 0) { s2.add(s1.pop()); } return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List } //方法:将 中缀表达式转成对应的List // s="1+((2+3)×4)-5"; public static List toInfixexpressionList(String s) { //定义一个List,存放中缀表达式 对应的内容 List ls = new ArrayList (); int i = 0; //这时是一个指针,用于遍历 中缀表达式字符串 String str; // 对多位数的拼接 char c; // 每遍历到一个字符,就放入到c do { //如果c是一个非数字,我需要加入到ls if((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57) { ls.add("" + c); i++; //i需要后移 } else { //如果是一个数,需要考虑多位数 str = ""; //先将str 置成"" '0'[48]->'9'[57] while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) { str += c;//拼接 i++; } ls.add(str); } }while(i < s.length()); return ls;//返回 } //将一个逆波兰表达式, 依次将数据和运算符 放入到 ArrayList中 public static List getListString(String suffixexpression) { //将 suffixexpression 分割 String[] split = suffixexpression.split(" "); List list = new ArrayList (); for(String ele: split) { list.add(ele); } return list; } //完成对逆波兰表达式的运算 public static int calculate(List ls) { // 创建给栈, 只需要一个栈即可 Stack stack = new Stack (); // 遍历 ls for (String item : ls) { // 这里使用正则表达式来取出数 if (item.matches("\d+")) { // 匹配的是多位数 // 入栈 stack.push(item); } else { // pop出两个数,并运算, 再入栈 int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else { throw new RuntimeException("运算符有误"); } //把res 入栈 stack.push("" + res); } } //最后留在stack中的数据是运算结果 return Integer.parseInt(stack.pop()); } } //编写一个类 Operation 可以返回一个运算符 对应的优先级 class Operation { private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; //写一个方法,返回对应的优先级数字 public static int getValue(String operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: System.out.println("不存在该运算符" + operation); break; } return result; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)