中缀表达式转后缀表达式(逆波兰式)

妖狐艹你老母 2024-03-22 11:17 41阅读 0赞

## 一. 什么是后缀表达式 ##

例如: a + b \* c + ( d \* e + f ) \* g , 这是日常中我们看到的简单计算表达式, 这就是一个中缀表达式.  
哪什么是后缀表达式呢? 上面这个中缀表达式又该如何转换成后缀表达式呢?

*  **将中缀表达式按照运算规则加上括号**
 *  **将括号内的运算符号放在对应括号外面**
 *  **去掉所有的括号**

例如上面的中缀表达式 a + b \* c + ( d \* e + f ) \* g

*  **将中缀表达式按照运算规则加上括号**  
    ( ( a + ( b \* c ) ) + ( ( ( d \* e ) + f ) \* g ) )
 *  **将括号内的运算符号放在对应括号外面**  
    ( ( a ( b c ) \* ) + ( ( ( d e ) \* f ) + g ) \* ) +
 *  **去掉所有的括号**  
    a b c \* + d e f + g \* +  
    **通过上面三步转换, 就让中缀表达式转为了后缀表达式, 最终的结果就是后缀表达式, 也叫做逆波兰式**

## 二. 逆波兰式的使用 ##

知道了如何变为一个逆波兰式, 也就是后缀表达式, 那么 怎么实现他呢? 例如很多带计算器功能的软件中, 用户输入的都是一个中序表达式, 计算机是通过后缀表达式来计算的, 因此如何用代码实现后缀表达式就至关 重要了.

用栈来模拟实现后缀表达式的计算结果 :

*  **遍历后缀表达式中非操作符( + - \* / ) 放入压栈**
 *  **遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数**
 *  **弹出的栈顶元素计算后重新压栈**
 *  **直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果**
 *  **遍历后缀表达式中非操作符( + - \* / ) 放入压栈**

![image.png][]此时遇到的 a b c 均为非操作符, 因此全部压栈, 直至遇到第一个操作符

*  **遇到操作符则从栈顶弹出两个元素, 第一个出栈的数为右操作数, 第二个出栈的数为左操作数**

![image.png][image.png 1]此时遇到了操作符 , \*\*因此弹出栈顶元素 c 作为右操作数, 弹出第二个栈顶元素 b 作为左操作数

那么, 为什么弹出的第一个栈顶元素时右操作数, 而不是左操作数呢 ?

\*\* **运算法则中, 加减乘除的优先级不同, 如果弹出得第一个元素为左操作数, 可能会因为运算法则的优先级, 导致最终结果错误**

例如 :  
计算表达式 : a + b \* c , a = 1, b = 2, c = 3 , 此时无论 左操作数是 b 还是 c 对于当前表达式都不会影响结果

当 变成 a + b - c 时, a = 1, b = 2, c = 3, b - c 中左操作数如果是 c 右操作数是 b 那么 b - c 就是正数; 同样 左操作数如果是 b 右操作数如果是 c 那么 b - c 就是负数, 会影响后面的计算结果

*  **弹出的栈顶元素计算后重新压栈**

![image.png][image.png 2]  
将出栈后的左操作数和右操作数计算后的结果重新入栈

*  **直至后缀表达式遍历完, 最后弹出栈顶的元素则为计算结果**

直至后缀表达式全部遍历完, 最后计算结果保存在栈顶中

## 三. LeetCode 逆波兰式练习 ##

了解逆波兰表达式如何来的以后, 就可以上力扣去挑战一下啦  
[leetCode - 逆波兰表达式][leetCode -](点击即可跳转)  
  
根据上面的逆波兰表达式的实现, 可以写出如下代码 :

class Solution {
        
        // 需要注意的是, 该题中是字符串数组
        public int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack<>();
            // 1. 遍历字符串数组判断该字符是否为操作符
            for(String s : tokens) {
        
                if(!isOperator(s)) {
        
                    // 2. 如果不是操作符, 当前元素就压栈    
                    stack.push(Integer.parseInt(s));
                }else {
        
                    // 3. 如果是操作符, 弹出栈顶元素, 第一个为右操作数, 第二个为左操作数
                    int num2 = stack.pop(); // num2 始终为右操作数
                    int num1 = stack.pop(); // num1 始终为左操作数
    
    
                    // 4. 计算完成后的结果进行压栈
                    switch(s) {
        
                        case "+" :
                            stack.push(num1 + num2);
                            break;
                        case "-" :
                            stack.push(num1 - num2);
                            break;
                        case "*" :
                            stack.push(num1 * num2);
                            break;
                        case "/" :
                            stack.push(num1 / num2);
                            break;
                    }
                }
            }
            // 5. 遍历结束后, 弹出栈顶元素即为所求结果
            return stack.pop();
        }
    
    
        // 判断是否为操作符
        private boolean isOperator(String s) {
        
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
        
                return true;
            }
            return false;
        }
    }

逆波兰表达式学会了, 就可以根据中序表达式简单的实现一个模拟计算器的功能啦, 可以试一试

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b73dc5f53f4640f2a55000361bd0a9a5.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ea8973e2afa647cc99cd3d767431b029.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a46c011f42234de2a9aa4be39d2522d5.png
[leetCode -]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/