[LeetCode]150.计算逆波兰表达式

用逆波兰表达式计算一个算术表达式的值。

有效的运算符仅为+、-、*和/。每个操作数可以是一个整数或另一个表达式。

注意：两个整数之间的除法应该取整。保证给定的 RPN 表达式总是有效的。这意味着该表达式总是会计算出一个结果，并且不会有任何除零操作。

示例 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

思路:

这是一道中等难度的题目。思路是遍历vector<int>的期间，遇到一个运算符就计算，遇到数字就入栈。把每一步的计算结果塞进一个stack<int>的临时栈中保存, 每次都取栈顶的两个数出来计算, 算好之后再把临时结果压入栈顶，全部计算完成之后——即完成原vector<int> tokens的遍历——再用stack<int>的top()函数直接返回计算结果。

AC代码:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        std::stack<int> tempStack;
        for (std::vector<string>::iterator it = tokens.begin() ; it != tokens.end(); ++it)
        {
            if((*it) == "+")
            {
                int op2 = tempStack.top(); 
                tempStack.pop();
                int op1 = tempStack.top(); 
                tempStack.pop();
                tempStack.push(op1+op2);
            }
            else if((*it) == "-")
            {
                int op2 = tempStack.top(); 
                tempStack.pop();
                int op1 = tempStack.top(); 
                tempStack.pop();
                tempStack.push(op1-op2);
            }
            else if((*it) == "*")
            {
                int op2 = tempStack.top(); 
                tempStack.pop();
                int op1 = tempStack.top(); 
                tempStack.pop();
                tempStack.push(op1*op2);
            }
            else if((*it) == "/")
            {
                int op2 = tempStack.top(); 
                tempStack.pop();
                int op1 = tempStack.top(); 
                tempStack.pop();
                tempStack.push(op1 / op2);
            }
            else
            {
                tempStack.push(std::stoi(*it));
            }
        }
        return tempStack.top();
    }
    
};