C++实现逆波兰表达式的例题详解

时间:2022-12-24 Albert Edison 人气:0

1. 题目描述

2. 解题思路

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出，它的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式，它严格遵循「从左到右」的运算。

在我们平时生活中，使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 )。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则将数字入栈；
如果不是数字，该字符则是运算符，如果遇到运算符，则将栈里面的两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数， 使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

3. 动图演示

来看个动图

4. 代码实现

有一点需要注意，num 1 和 num2 进行运算的时候，num1 是右操作数，num2 是左操作数，别写反了！！！

代码示例

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                auto num1 = st.top();
                st.pop();
                auto num2 = st.top();
                st.pop();

                if (str == "+") {
                    st.push(num2 + num1);
                }
                else if (str == "-") {
                    st.push(num2 - num1);
                }
                else if (str == "*") {
                    st.push(num2 * num1);
                }
                else if (str == "/") {
                    st.push(num2 / num1);
                }
            }
            else {
                st.push(stoi(str)); // 如果是操作数就入栈，因为这是字符，所以要转成数字
            }
        }
        return st.top();
    }
};

加载全部内容