224-基本计算器

LeetCode 224. 基本计算器

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

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

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

示例 2：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

method: 栈

只有+和-，可以直接去掉括号

• +就sign=st.top
• -就取反，sign=-st.top
• (就将sign入栈
• )就出栈
• 数字就合并起来

int calculate(string s) {
    stack<int> ops;
    int sign = 1;
    ops.push(sign);
    int i = 0;
    int n = s.size();
    int res = 0;
    while (i < n) {
        if (s[i] == ' ') i++;
        else if (s[i] == '+') {
            sign = ops.top();
            i++;
        } else if (s[i] == '-') {
            sign = -ops.top();  // 取反
            i++;
        } else if (s[i] == '(') {
            ops.push(sign);
            i++;
        } else if (s[i] == ')') {
            ops.pop();
            i++;
        } else {
            long num = 0;
            while (i < n && s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
                i++;
            }
            res += sign * num;
        }
    }
    return res;
}

---

LeetCode 227. 基本计算器 II

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

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3+5 / 2 "
输出：5

method: 栈

• 如果是数字就合并起来
• 不是数字也不是空格，或者是最后一个字符，需要看前一个符号
  • 如果前一个符号是+-，将num或-num入栈
  • 如果前一个符号是*/，将栈顶元素与当前数字相乘或除

int calculate(string s) {
    vector<int> st;
    char preSign = '+';
    int n = s.size();
    long num = 0;
    for (int i = 0; i < n; i++) {
        if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
        } 
        if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
            switch (preSign) {
                case '+':
                    st.push_back(num);	// 将num压栈
                    break;
                case '-':
                    st.push_back(-num);	// 将-num压栈
                    break;
                case '*':
                    st.back() *= num;	// 栈顶直接乘以num
                    break;
                default:
                    st.back() /= num;	// 栈顶直接除以num
            }
            preSign = s[i];
            num = 0;
        }
    }
    int res = 0;
    for (auto n : st) res += n;
    return res;
}

---

LeetCode 772. 基本计算器 III

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。

你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。

示例 1：

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

示例 2：

输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21

method

在上一题的基础上增加了括号，对于括号内的计算可以直接用上一题的解法，所以碰到括号就递归计算内的结果

递归计算的时候会改变指针位置，需要返回计算结果和改变后的指针

因为指针会改变，所以需要一开始就记录s[i]

vector<int> dfs(string& s, int index) {
    vector<int> st;
    vector<int> res(2);
    int n = s.size();
    int num = 0;
    char preSign = '+';
    for (int i = index; i < n; i++) {
        char c = s[i];
        if (isdigit(c)) {
            num = num * 10 + c - '0';
        }
        if (c == '(') {
            vector<int> next(dfs(s, i + 1));
            num = next[0];
            i = next[1];
        }
        if ((!isdigit(c) && c != '(') || i == n - 1) {
            switch (preSign) {
                case '+':
                    st.push_back(num);
                    break;
                case '-':
                    st.push_back(-num);
                    break;
                case '*':
                    st.back() *= num;
                    break;
                default:
                    st.back() /= num;
            }
            if (c == ')') {
                res[1] = i;
                break;
            }
            preSign = c;
            num = 0;
        }
    }
    for (auto n : st) res[0] += n;
    return res;
}

int calculate(string s) {
    vector<int> res = dfs(s, 0);
    return res[0];
}