LeetCode 0150. Reverse Polish Expression Evaluation

【LetMeFly】150.逆波兰表达式求值

力扣题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

根据 逆波兰表示法,求表达式的值.

有效的算符包括 +、-、*、/ .每个运算对象可以是整数,也可以是另一个逆波兰表达式.

注意 两个整数之间的除法只保留整数部分.

可以保证给定的逆波兰表达式总是有效的.换句话说,表达式总会得出有效数值且不存在除数为 0 的情况.

 

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"）,或是在范围 [-200, 200] 内的一个整数

 

逆波兰表达式：

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面.

• 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) .
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) .

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果.
• 适合用栈操作运算：遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

方法一：栈模拟

If you understand what is a reverse Polish expression,Then this question will be very simple.

The calculation of the reverse Polish expression is much easier than finding the reverse Polish of the expression.

使用一个栈,

遍历逆波兰表达式,如果遇到运算符,The corresponding number of elements are removed from the stack,并进行运算,再把结果入栈.

例如,如果遇到了+,Just remove two elements from the stack（Because the plus sign is a binary operator）,Sum and push the result onto the stack.

注意,The order in the stack is reversed from the original order,The last element is popped first.

如果遇到数字,On the stack between.

• 时间复杂度$O(n)$,其中$n$is the element in the Reverse Polish expression/number of operators
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
    
public:
    int evalRPN(vector<string>& tokens) {
    
        stack<int> st;
        for (string& s : tokens) {
    
            if (s == "+" || s == "-" || s == "*" || s == "/") {
    
                int second = st.top();
                st.pop();
                int first = st.top();
                st.pop();
                if (s == "+")
                    st.push(first + second);
                else if (s == "-")
                    st.push(first - second);
                else if (s == "*")
                    st.push(first * second);
                else if (s == "/")
                    st.push(first / second);
            }
            else {
    
                st.push(atoi(s.c_str()));
            }
        }
        return st.top();
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126084278