224. 基本计算器 类文法解析类的（使用栈）

224. 基本计算器

两个栈，一个存数字，一个存内容

class Solution {
public:
    int calculate(string s) {
        stack<int> stk, num;
        string str;
        for (int i = 0; i < s.size(); i++) {
            int j = i;
            while (isdigit(s[j])) {
                j++;
            }
            if (j > i) {
                str += " " + s.substr(i, j - i);
                i = j - 1;
            } else {
                str += " ";
                str += s[i];
            }
        }
        stringstream ssin(str);

        string cur;
        int sign = 1;
        num.push(0);
        while (ssin >> cur) {
            if (cur == "(") {
                stk.push(sign);
                num.push(0);
                sign = 1;
            } else if (cur == ")") {
                int t = num.top() * stk.top();
                num.pop();
                stk.pop();
                num.top() += t;
            } else if (cur == "+")sign = 1;
            else if (cur == "-")sign = -1;
            else {
                int t = sign * atoi(cur.c_str());
                num.top() += t;
            }
        }

        return num.top();
    }
};

来自 Shopee 2021秋招部分笔试题汇总T3

给定一个字符串式子，返回它的计算结果。算术规则为: k*[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。e.g. s = "3*[a2*[c]]", 返回 “accaccacc”

class Solution {
public:
    string computeString(string str) {
        stack<int> num;
        stack<string> stk;
        num.push(1);
        stk.push("");
        for (int i = 0; i < (int) str.size(); i++) {
            if (isalpha(str[i])) {
                stk.top() += str[i];
                continue;
            } else if (str[i] == ']') {
                int cnt = num.top();
                num.pop();
                string t = stk.top();
                stk.pop();
                string ss;
                while (cnt--) {
                    ss += t;
                }
                stk.top() += ss;
                continue;
            }
            int j = i;

            while (isdigit(str[j]))j++;
            // str[j]=='*'
            if (j > i) {
                string t = str.substr(i, j - i);
                int cnt = atoi(t.c_str());
                num.push(cnt);
                stk.push("");
                i = j + 1;
            }
        }
        return stk.top();
    }
};