高频笔试题_栈和队列

为什么把这两道题摆在这里，是因为第二题可以在第一题上找到灵感。
第一题就是简单的四则运算，而第二题可以建立两个栈，一个用来存数字，一个用来存字符串
这两道题出现在笔试面试的频率还是很高的，需要注意，尤其是第二题，没有想象中那么容易
逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> sk;
        for(int i=0; i<tokens.size(); i++) {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = sk.top();
                sk.pop();
                int num2 = sk.top();
                sk.pop();

                if(tokens[i] == "+") {
                    sk.push(num2 + num1);
                }
                if(tokens[i] == "-") {
                    sk.push(num2 - num1);
                }
                if(tokens[i] == "*") {
                    sk.push(num2 * num1);
                }
                if(tokens[i] == "/") {
                    sk.push(num2 / num1);
                }
            }else {
                sk.push(stoi(tokens[i]));
            }
            
        }
        int res = sk.top();
        sk.pop();
        return res;
    }
};

字符串解码

class Solution {
public:
    string decodeString(string s) {
        stack<int> num_stk;//数字栈
        stack<string> str_stk;//字符串栈
        string str;//当前正在累积的字符串
        for(int i=0; i<s.size(); i++){
            if(isdigit(s[i])){//遇到数字
                int n = s[i]-'0';
                while(isdigit(s[++i])){//数字可能有多位
                    n = 10*n + s[i] - '0';
                }
                num_stk.push(n);//加入数字栈
                i--;//往后退一步(for循环处有自增操作)
            }
            else if(s[i] == '['){//遇到左括号
                str_stk.push(str);//将当前累积的字符串入栈
                str = "";//开始记录新的一段字符串
            }
            else if(s[i] == ']'){//遇到右括号
                string tmp;
                //将当前字符串按数字栈栈顶元素为倍数进行扩展
                for(int i=0; i<num_stk.top(); i++){
                    tmp += str;
                }
                str = tmp;
                num_stk.pop();//数字栈栈顶元素弹出
                //字符串栈栈顶元素弹出来并与当前字符串拼接，作为新的当前正在累积的字符串
                str = str_stk.top()+str;
                str_stk.pop();
            }
            else{
                str += s[i];//当前字符串继续累积
            }
        }
        return str;
    }
};