LeetCode每日一题-3.20-150-逆波兰表达式求值

  • 时间:
  • 浏览:
  • 来源:互联网

所谓逆波兰表达式就是后缀表达式,奇怪的知识又增加了。

题目描述

在这里插入图片描述

思路 栈

因为题目说了保证是合法的表达式,所以不需要关心不符合题意的情况

  1. 遇到数字,将字符串转换为数字,存入栈中
  2. 遇到字符,从栈取出两个数字,第一个作为第二个运算数,第二个作为第一个运算数,将结果存入栈中。

最后栈首就是结果。
所以难点还是**“将字符串转换为数字”**,如果这题是char会舒服很多,但偏偏就是要用string。
ps:其实也可以使用s[0] - ‘0’。
这就考察了对stoi/atoi函数的掌握程度。大致来说,这两个函数这样就可以用了:

	string a = "3";
	int num1 = atoi(a.c_str());
	string b = "3";
	int num2 = stoi(b);

然后要注意的就是,switch语句不能直接判断string,所以我们使用s[0],得到char类型再去判断。
为了严谨使用atoi和stoi:这两个函数分别针对const string & sconst char & c类型转换,这里我们for循环就用对应类型遍历,也可以直接用string。

class Solution {
public:
    bool isNumber(string s) {
        if(!(s == "+" || s == "-" || s == "*" || s == "/")) {
            return true;
        }
        return false;
    }
    int evalRPN(vector<string>& tokens) {
        //存放数字的堆栈
        stack<int> s;
       //这里用for(string c : tokens)也是对的 
        for(const string& c : tokens) {
            if(isNumber(c)) {
                s.push(stoi(c));
            } else {
                int tmp;
                int b = s.top();
                s.pop();
                int a = s.top();
                s.pop();
                switch(c[0]) {
                case '+':
                    tmp = a + b;
                    break;
                case '-':
                    tmp = a - b;
                    break;
                case '*':
                    tmp = a * b;
                    break;
                default:
                    tmp = a / b;
                }
                s.push(tmp);
            }
        }
        return s.top();
    }
};

时间复杂度O(n)
空间复杂O(n)

本文链接http://www.dzjqx.cn/news/show-617106.html