基本计算器 --- 每日一题

224. 基本计算器

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

输入:s = "1 + 1"
输出:2

注意:s 由数字、'+'、'-'、'('、')'、和 ' ' 组成,表达式必定有效

思路

  • 用1, -1表示正负号
  • 一旦遇到 '(', 表示右边表达式开始,res=0,sign=1,并将原有入栈
  • 遇到 ')',表示当前表达式结束,pop栈元素计算
class Solution {
public:
    int calculate(string s) {
        int res = 0;
        int sigh = 1;
        int num = 0;
        stack<int> sk;
        for (char ch : s) {
            if (ch >= '0' && ch <= '9') {
                num = num * 10 + (ch -'0');
            } else if (ch == '+' || ch == '-') {
                res += sigh * num;
                num = 0;
                if (ch == '+') {
                    sigh = 1;
                } else {
                    sigh = -1;
                }
            } else if (ch == '(') {
                sk.push(res);
                sk.push(sigh);
                res = 0;
                sigh = 1;
            } else if (ch == ')') {
                res += sigh * num;
                num = 0;
                res *= sk.top();
                sk.pop();
                res += sk.top();
                sk.pop();
            }
        }
        res += sigh*num;
        return res;
    }
};

227. 基本计算器 II

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        int right = n-1;
        while (s[right] == ' ') {
            right--;
        }
        stack<int> sk;
        char sign = '+';
        int num = 0;
        int pre = 0;
        for (int i = 0; i <= right; i++) {
            if (s[i] == ' ') {
                continue;
            }
            if (s[i] >= '0' && s[i] <= '9') {
                num = num*10 + (s[i] - '0');
            }
            if (!(s[i] >= '0' && s[i] <= '9') || i == right) {
                switch(sign) {
                    case '+': 
                        sk.push(num);
                        break;
                    case '-':
                        sk.push(-num);
                        break;
                    case '*':
                        pre = sk.top();
                        sk.pop();
                        sk.push(pre * num);
                        break;
                    case '/':
                        pre = sk.top();
                        sk.pop();
                        sk.push(pre/num);
                        break;
                }
                sign = s[i];
                num = 0;
            }
        }
        int res = 0;
        while (!sk.empty()) {
            res += sk.top();
            sk.pop();
        }
        return res;
    }
};

评论

暂无评论