一、中缀表达式
1.是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)
2.与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。
3.与前缀或后缀记法不同的是,中缀记法中括号是必需的。
二、格式化表达式
如果原封不动的遍历表达式字符串(10+20/2*3)/2+8
将得到如下结果:
[(, 1, 0, +, 2, 0, /, 2, *, 3, ), /, 2, +, 8]
最好的分隔结果是:[(, 10, +, 20, /, 2, *, 3, ), /, 2, +, 8]
思路:将字符串格式化为如下情形,再进行分隔即可
#(#10#+#20#/#2#*#3#)#/#2#+#8
三、栈实现中缀表达式
创建两个栈 :operatorStack(操作符栈) 和 numberStack(数字栈)
四、代码实现
package p2.线性结构; public class InfixCalculator { public static void main(String[] args) { String expression = "(10+20/2*3)/2+8"; try { int result = evaluateExpression(expression); System.out.println(result); }catch(Exception e){ e.printStackTrace(); System.out.println("Wrong expression:"+expression); } } private static int evaluateExpression(String expression) { //需要两个辅助栈 ArrayStack<Character> operatorStack = new ArrayStack<>(); ArrayStack<Integer> numberStack = new ArrayStack<>(); //格式化表达式 expression = insertBlanks(expression); String[] tokens = expression.split(" ");//字符串用空格切割 for (String token : tokens) {//token===tokens[i] //过滤空串,切割出来的字符有的是空串(有字符串无内容,即长度是0) 空串不是null,null为空 啥都没有 if (token.length() == 0) { continue; //遍历到 + - 号 } else if (token.equals("+") || token.equals("-")) {//token是字符串,拿equals来比较的 operatorStack是存字符的栈,里面元素都是字符,是拿字符进行比较 while (!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) { //如果之前是别的 + - * / 需要弹栈并计算 processAnOperator(numberStack, operatorStack);//可能需要进行几次,所以是while 循环,一直到栈弹空了或者不是其他加减乘除再进栈 如开始栈里有+ *,要进来+,需要两次 } //如果操作符栈为空 或者 不为空 但栈为( operatorStack.push(token.charAt(0));// operatorStack是存字符的,token是字符串,放不进去的,要把字符放进去 //遍历到 * / 号 } else if (token.equals("*") || token.equals("/")) { while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) { //如果之前是别的 * / 需要弹栈并计算 processAnOperator(numberStack, operatorStack); } //如果操作符栈为空 或者 不为空 但栈为( operatorStack.push(token.charAt(0)); //遍历到( } else if (token.equals("(")) { operatorStack.push(token.charAt(0)); } else if (token.equals(")")) { //只要操作符栈的栈顶不是左括号( 就挨个弹栈计算即可 while (operatorStack.peek() != '(') { processAnOperator(numberStack, operatorStack); } //最后清掉左括号 operatorStack.pop(); //遍历到数字 } else { //numberStack.push(Integer.parseInt(token)); 把数字字符串解析成一个数字 通过Integer的静态方法 或 new Integer numberStack.push(new Integer(token));//根据一个数字字符串去创建一个Integer对象 } } //处理最后面的操作符 while (!operatorStack.isEmpty()) { processAnOperator(numberStack, operatorStack); } return numberStack.pop();//计算的最后结果肯定在数字栈里面,把这个元素弹栈即可 } //操作符栈弹栈一个元素,数字栈弹栈两个数字 并将新的结果进栈到数字栈 private static void processAnOperator(ArrayStack<Integer> numberStack, ArrayStack<Character> operatorStack) { char op=operatorStack.pop(); int num1=numberStack.pop(); int num2=numberStack.pop(); //num2 op num1 数字先弹出来的放操作符右边,后弹出来的放操作符左边,操作符只弹一个,放中间 if(op=='+'){ numberStack.push(num2+num1); }else if(op=='-'){ numberStack.push(num2-num1); }else if (op=='*'){ numberStack.push(num2*num1); }else{ numberStack.push(num2/num1); } } //对原表达式进行格式化,给所有的非数字字符两边添加空格 private static String insertBlanks(String expression) { /* “(10+20/2*3)/2+8” “ ( 10 + 20 / 2 * 3 ) / 2 + 8” 字符串跟数组一样,一个字符串一旦创建出来,其内容 长度不能改变,我们不可能在原字符串上进行增、删、改 (可查)所以需遍历出一个新字符串 */ StringBuilder sb = new StringBuilder(); for (int i = 0; i < expression.length(); i++) { char c = expression.charAt(i);//先从左到右把字符取出来,往c这个字符里面放 if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') { sb.append(' '); sb.append(c); sb.append(' '); } else { sb.append(c); } } return sb.toString(); } }