代码随想录-DAY⑨-栈与队列——leetcode 20 | 150

20

思路

遇到左括号压栈，
遇到右括号弹栈，
并对比是否配对。
注意需要弹栈时栈空的话说明也不匹配。

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

代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> lefttk;
        for(auto ch : s){
            switch(ch){
                case '(':
                case '[':
                case '{':
                lefttk.push(ch);
                break;
                default:
                if (lefttk.empty()){
                    return false;
                }
                if (ch - lefttk.top() > 3 || ch - lefttk.top() < 0){
                    return false;
                }
                lefttk.pop();
                break;
            }
        }
        return lefttk.empty();
    }
};

150

思路

数字则压栈，
运算符则取出两个栈顶元素并做计算，
然后把计算结果压栈。
最后返回栈顶。

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

代码

class Solution {
public:
    bool isNumber(string& token){
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> cclt;
        for(auto token : tokens){
            if(isNumber(token)){
                cclt.push(atoi(token.c_str()));
            }
            else{
                int num1 = cclt.top();
                cclt.pop();
                int num2 = cclt.top();
                cclt.pop();
                switch(token[0]){
                    case '+':
                    cclt.push(num2+num1);
                    break;
                    case '-':
                    cclt.push(num2-num1);
                    break;
                    case '*':
                    cclt.push(num2*num1);
                    break;
                    case '/':
                    cclt.push(num2/num1);
                    break;
                }
            }
        }
        return cclt.top();
    }
};

原文地址：https://blog.csdn.net/weixin_43160551/article/details/140451818

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！