150.Evaluate Reverse Polish Notation

topic
792 词

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.

思路分析

  逆波兰表示法，又称为后缀表示法，是一种不需要括号的一种四则运算表示法。比如：9 3 1 - 3 * + 10 2 / + ，就是一种后缀表示法。计算方法就使用栈，遇到数字就入栈，遇到符号就弹出栈顶的两个数字并将这两个数字的计算结果压入栈中。

实现细节

  1. 字符串转整型函数stoi()
  2. 整型函数转字符串to_string()

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class  {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int number;
        string symbols = "+-*/";
        for(auto token: tokens){
            if(symbols.find(token) != string::npos){
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                if(token == "+") stk.push(num1+num2);
                if(token == "-") stk.push(num1-num2);
                if(token == "*") stk.push(num1*num2);
                if(token == "/") stk.push(num1/num2);
            }
            else{
                number = stoi(token);
                stk.push(number);
            }
        }
        return stk.top();
    }
};