中缀表达式转换后缀表达式简易方法(逆波兰表达式)

忘是亡心i 2023-10-03 19:54 13阅读 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  \*\+

#### 例题：逆波兰表达式求值 ####

力扣例题链接：[力扣][Link 1]

本题思路：如果是数字就入栈，如果是运算符号就弹出栈上的最上面两个元素，将其运算，再进行入栈。并循环直至字符串组遍历完成。最后弹出栈中仅有的一个元素

例如：

tokens = ["2","1","+","3","*"]

那就是 2 入栈，1入栈 +不是数字，弹出2和1，运算2+1=3，再将3入栈 ，下一个3入栈 \*不是数字，弹出3和3 ，运算3\*3=9 ，入栈

最后出栈 9 为运算结果

tokens = ["4","13","5","/","+"]

4入栈，13入栈，5入栈，/不是数字，弹出5和13，运算13/5=2，2入栈，+不是数字，弹出2和4

运算2+4 = 6，6入栈。

最后出栈6为结果

class Solution {
        public static boolean isop(String x){
            if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
                return true;
            }
            else {
                return false;
            }
    
        }
        public int evalRPN(String[] tokens) {
             Stack<Integer> stack = new Stack<Integer>();
            for(int i = 0;i<= tokens.length-1;i++){
                String x = tokens[i];
                if(!isop(x)){
                    stack.push(Integer.parseInt(x));
                }
                else{
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch (x){
                        case "+":stack.push(num1+num2);break;
                        case "-":stack.push(num1-num2);break;
                        case "*":stack.push(num1*num2);break;
                        case "/":stack.push(num1/num2);break;
                    }
                }
            }
            return stack.pop();
        }
    
        }

[Link 1]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/