LeetCode 150:计算逆波兰式（后缀表达式）的值

运算符仅包含”+”,”-“,”*“和”/“，被操作数可能是整数或其他表达式
例如：
[“2”, “1”, “+”, “3”, “*“] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/“, “+”] -> (4 + (13 / 5)) -> 6

这道题整体思路就是使用栈，对于字符串进行处理，
1.遇到数字直接压入栈，注意这里为char类型的数字，所以需要转换为int

2.遇到”+”,”-“,”*“和”/“符号时，将栈中的两个数字弹出进行计算，再压入栈中

3.最后直到字符串处理完，栈中只剩下一个数字，得到结果

Code

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if(tokens.size() == 0)
        {
            return 0;
        }
        
        stack<int> numbers;
        
        for(int i=0;i < tokens.size();i++)
        {
            string s = tokens[i];
            if(s == "+"||s == "-"||s == "*"||s == "/")
            {
                if(numbers.size() < 2) 
                {
                    return 0;//计算结果时，stack至少2个数，否则不合法，返回0
                }
                
                int num2 = numbers.top();
                numbers.pop();
                int num1 = numbers.top();
                numbers.pop();
                
                int result;
                
                if(s == "+")
                    result = num1 + num2;
                else if(s == "-")
                    result = num1 - num2;
                else if(s == "*")
                    result = num1 * num2;
                else if(s == "/")
                    result = num1 / num2;
                
                numbers.push(result);
            }
            else
            {
                stringstream ss; //字符串转数字技巧
                ss<<s;
                int temp;
                ss>>temp;
                numbers.push(temp);
            }
        }
        return numbers.top();
    }
};

C++ 栈 Stack

Code

#include <stack> //头文件

stack<int>  stack1;   //定义类型为int的空栈

empty()     //堆栈为空则返回真
pop()       //移除栈顶元素,没有返回值!!!
push()      //在栈顶增加元素,没有返回值
size()      //返回栈中元素数目
top()       //top函数的返回值是栈顶元素,注意并没有删掉栈顶元素!!