计算表达式，中缀表达式转后缀表达式步骤详解以及代码实现（Java）

计算表达式，中缀表达式转后缀表达式步骤详解以及代码实现（Java） 计算表达式，中缀表达式转后缀表达式步骤详解以及代码实现（Java）

所谓的前、中、后缀表达式，简单阐述中缀表达式和后缀表达式：

• 中缀表达式：常常人们书写的表达式就是中缀表达式，例如：4*(1 + 2) - 3，就是我们平常所使用表达式，对于人来说，中缀表达式通俗易懂，知道怎样计算这个算式，容易理解计算步骤的优先级，那么对于计算机来说，怎样理解这个算式的优先级呢。（所谓优先级就是先计算小括号里的算式，再计算乘除后加减）
• 后缀表达式：后缀表达式也称之为逆波兰表达式，若将上述例子的中缀表达式转换成后缀表达式可表示为：4 1 2 + * 3 -,对于计算机来说很容易理解后缀表达式的运算优先级，即从左到右先扫描到的 *** 作符先运算，比如上述后缀表达式先执行 “+”，再执行 “*”，后执行 “-” 法运算。具体执行情况见下面计算后缀表达式步骤。

中缀表达式转后缀表达式步骤

1. 初始化两个栈：运算符栈s1和储存中间结果栈s2；

2. 从左到右扫描中缀表达式；

3. 遇到 *** 作数时，将其压入s2；

4. 遇到运算符时，比较其与s1栈顶运算符的优先级；

   4.1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

   4.2. 否则，若优先级比栈顶的运算符高，也将运算符压入s1；

   4.3. 否则（即优先级同级或者小），将s1栈顶的运算符d出并压入s2中，再次转到4.1与新的栈顶运算符相比较；

5. 遇到括号时；

6. 重复2到5步骤，直到表达式的最右边；

7. 将s1中剩余的运算符依次d出并压入s2；

8. 依次d出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例说明

假如中缀表达式为：1 + ((2 + 3)*4) - 5 转为后缀表达式为：1 2 3 + 4 * + 5 -

扫描到的元素s1（栈底->栈顶）s2（栈底->栈顶）说明1空1扫描到数字直接压入s2栈++1s1在这之前为空，直接压入元素+号(+ (1扫面到的元素为左括号则直接入s1栈(+ ( (1扫面到的元素为左括号则直接入s1栈2+ ( (1 2扫描到数字直接压入s2栈++ ( ( +1 2栈顶为左括号，直接将扫描到的元素压入s1栈3+ ( ( +1 2 3数字 直接入s2栈)+ (1 2 3 +右括号，依次d出s1栈顶元素并压入到s2栈中，
直到遇到左括号，并丢弃该对括号*+ ( *1 2 3 +栈顶为左括号，直接压入元素4+ ( *1 2 3 + 4数字 直接压入s2栈)+1 2 3 + 4 *右括号，依次d出s1栈顶元素并压入到s2栈中，
直到遇到左括号，并丢弃该对括号--1 2 3 + 4 * +与栈顶比较 优先级不高于栈顶元素 则d出栈顶元素至s2
再与新的栈顶元素比较 栈顶为空 压入减号5-1 2 3 + 4 * + 5数字 直接压入s2栈扫描到达右端空1 2 3 + 4 * + 5 -扫描到达右端后，将s1栈中剩余的元素依次d出并压入到s2栈中 中缀表达式转后缀表达式代码实现

import java.util.*;


class InfixToPostexpression {
    
    
    public static Stack switchList(String infixexpression) {
        // 字符串分割成数组
        // 遍历数组代替扫描表达式
        List list = InfixToPostexpression.toList(infixexpression);
        System.out.println(list);
        Stack numStack = new Stack<>();
        Stack operateStack = new Stack<>();
        
        for (int i = 0; i < list.size();) {
            // 逐个取出列表中的元素
            String element = list.get(i);
            if (element.charAt(0) >= '0' && element.charAt(0) <= '9') {// 如果是数字直接压到numStack
                numStack.push(element);
                i++;
            }
            else if (operateStack.isEmpty()) {// 如果栈空直接将元素压入栈
                operateStack.push(element);
                i++;
            }
            else if (element.equals("+") || element.equals("-") || element.equals("*") || element.equals("/")) {// 如果为运算符 则比较优先级
                if (operateStack.peek().equals("(") || operateStack.isEmpty()) {// 如果栈为空或者栈顶元素为左括号 则直接该元素压入operateStack栈中
                    operateStack.push(element);
                    i++;
                }
                // 如果当前运算符高于栈顶运算符 则直接将当前运算符压入operateStack栈中
                else if ((element.equals("*") || element.equals("/")) && ((operateStack.peek().equals("+")) || (operateStack.peek().equals("-")))) {
                    operateStack.push(element);
                    i++;
                }
                else { // 否则 当前运算符优先级不大于栈顶运算符的优先级 则将栈顶运算符弹出压入到numStack栈中 再将当前运算符与下一个栈顶元素比较优先级 则i不递增
                    numStack.push(operateStack.pop());
                }
            }
            else if (element.equals("(")){  // 如果当前元素为左括号 则直接压入operateStack栈中
                operateStack.push(element);
                i++;
            }
            else if (element.equals(")")) {  // 如果当前元素为右括号 依次将栈顶元素弹出压到numStack栈中 直到弹出元素为左括号 然后丢弃这一对括号
                while (!(operateStack.peek().equals("("))) {
                    numStack.push(operateStack.pop());
                }
                operateStack.pop();
                i++;
            }
        }
        
        // 当中缀表达式从左到右扫描完后 执行一下步骤
        // 把operateStack中剩余的元素弹出压到numStack栈中
        while (!operateStack.isEmpty()) {
            numStack.push(operateStack.pop());
        }
        
        // 再将numStack的元素顺序反转 即为后缀表达式
        while (!numStack.isEmpty()) {
            operateStack.push(numStack.pop());
        }
        
        return operateStack;
    }
    
    
    public static List toList(String str) {
        List list = new ArrayList<>();
        
        String s = "";
        for (int i = 0; i < str.length(); i++) {
            // 如果是运算符 直接添加到列表中
            if ((str.charAt(i) >=  '9' || str.charAt(i) <= '0') && str.charAt(i) != ' ')
                list.add(str.charAt(i) + "");
            else if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {  // 如果该字符是数字 需要处理是不是多位数
                s += str.charAt(i);
                // 如果字符串没有到达边界 且下一个字符也是数字就进行拼接
                if (i + 1 >= str.length()  || str.charAt(i + 1) < '0' || str.charAt(i + 1) > '9') {
                   list.add(s);
                   s = "";
                }
            }   
        }
        
        return list;
    }
}

转换得到后缀表达式，对于写程序来计算后缀表达式相当简单，以下为具体的就算过程：

计算后缀表达式步骤

• 创建一个栈储存中间的计算结果，假如栈名为 stack
• 从左至右扫描后缀表达式
  • 若为数字，将数字压入到stack栈中
  • 若为运算符，依次d出栈顶两个数字进行响应的运算，将运算结果压入stack栈中

• 直到扫描完后缀表达式，最后stack栈中只剩一个数，即为计算结果

举例说明

以上述后缀表达式为例：1 2 3 + 4 * + 5 -

扫描到的元素stack栈中的动态示意说明11数字直接入栈21 2数字直接入栈31 2 3数字直接入栈+1 5d出3、2 ，将2 + 3结果压入栈中41 5 4数字直接入栈*1 20d出5，4， 将4 * 5结果压入栈中+21d出20，1，将1 + 20结果压入栈中521 5数字直接入栈-16d出5，21 将21 - 5结果压入栈中

扫描后缀表达式到达右端后，satck栈中只剩一个元素为16，即最后栈中的元素为计算后缀表达式的结果

计算后缀表达式的代码实现

import java.util.*;


public class CalculateWithPostexpression {
    
    public double culculate(String str) {
        // 将中缀表达书转换成后缀表达式
        Stack stack = InfixToPostexpression.switchList(str);
        Stack numberStack = new Stack<>();
        
        // 根据后缀表达式的计算步骤计算
        // 1.从左到右扫描后缀表达式 
        // 2.若为数字就压入栈中 
        // 3.若为 *** 作符则依次d出两个栈顶元素进行响应的运算,将运算结果压入栈中
        // 4.扫描结束后 栈中仅剩的一个元素即为表达式的计算结果
        int count = stack.size();
        for (int i = 0; i < count; i++) {
            // 如果为数字直接压栈
            if (stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <= '9') {
                numberStack.push(Double.valueOf(stack.pop()));
            }
            else {  // 否则 进行相应的操作
                double num1 = (double)numberStack.pop();  // 弹出栈顶的数字
                double num2 = (double)numberStack.pop();
                switch (stack.pop()) {  // 进行相应的运算
                    case "+" : numberStack.push(num2 + num1);break;
                    case "-" : numberStack.push(num2 - num1);break;
                    case "*" : numberStack.push(num2 * num1);break;
                    case "/" : numberStack.push(num2 / num1);break;
                    default : throw new RuntimeException("输入的表达有误");
                }         
            }
        }
        
        return (double)numberStack.pop();  // 返回栈中最后一个元素，即为计算结果
    }
}

总结

想要计算机以人们的预期来理解中缀表达式的优先级，然后计算中缀表达式，此举并不简单，但是计算后缀表达式对于写程序来实现先对简单。但是难点在于中缀表达式转换成后缀表达式，当然，如果觉得转换过程麻烦，或者不理解亦或看不懂实现转换的代码，也有直接计算中缀表达式的方法，以及代码实现，等我更新。。。