LeetCode #150：Evaluate Reverse Polish Notation(后缀表达式求值)

题目描述

逆波兰式，更为人所知的名字是 “后缀表达式”。所谓后缀就是指运算算符写在操作数后面，我们平时习惯的 “中缀表达式” 是将运算符写在两个操作数之间。由于计算机内部就是采用后缀表达式的算法来计算表达式的值，所以实现此算法有着很高的现实意义。

要求后缀表达式的值，我们需要顺序扫描表达式的每一项，然后根据每一项的类型做对应的操作：若该项是操作数，将其压入工作栈中；若该项是操作符 op，则连续从栈中弹出两个操作数 y 和 x，计算 x op y，再将结果重新压入工作栈中。当表达式的所有项都扫描完后，工作栈顶存放的元素就是该表达式的结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        for(int i = 0; i < tokens.size(); i ++) {
            if(tokens[i] == "+") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(x + y);
            } else if(tokens[i] == "-") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(x - y);
            } else if(tokens[i] == "*") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(x * y);
            } else if(tokens[i] == "/") {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(x / y);
            } else {
                s.push(stoi(tokens[i]));
            }
        }

        return s.top();
    }

    stack<int> s;
};