解题思路

为了实现一个支持加、减、乘和括号的整数计算器，我们可以使用递归来处理运算符的优先级和括号的嵌套。具体步骤如下：

  1. 递归计算：

    • 使用递归函数来处理括号内的表达式。
    • 通过遍历字符串，构建当前数字和运算符。

  2. 处理运算符：

    • 根据当前运算符更新结果。
    • 处理括号时，递归调用计算函数。

  3. 返回结果：

    • 在遍历结束后，返回最终计算结果。

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int getRes(int resSofar, char sign, int num) {
        if (sign == '+') return resSofar + num;
        if (sign == '-') return resSofar - num;
        return resSofar * num;
    }

    int calca(string s) {
        char sign = '+';
        int num = 0;
        int resCur = 0;
        int res = 0;
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            char ch = s[i];
            if (isdigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            else if (ch == '(') {
                int cnt = 1;
                int j = i + 1;
                while (j < n) {
                    if (s[j] == '(') cnt++;
                    else if (s[j] == ')') cnt--;
                    if (cnt == 0) {
                        num = calca(s.substr(i + 1, j - i - 1));
                        break;
                    }
                    j++;
                }
                i = j;
            }
            if (ch == '+' || ch == '-' || ch == '*' || i == n - 1) {
                resCur = getRes(resCur, sign, num);
                if (ch == '+' || ch == '-' || i == n - 1) {
                    res += resCur;
                    resCur = 0;
                }
                sign = ch;
                num = 0;
            }
            i++;
        }
        return res;
    }
};

int main() {
    string s;
    Solution sol;
    while (cin >> s) {
        try {
            cout << sol.calca(s) << endl;
        } catch(...) {
            break;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int getRes(int resSofar, char sign, int num) {
        if (sign == '+') return resSofar + num;
        if (sign == '-') return resSofar - num;
        return resSofar * num;
    }
    
    public static int calca(String s) {
        char sign = '+';
        int num = 0;
        int resCur = 0;
        int res = 0;
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            else if (ch == '(') {
                int cnt = 1;
                int j = i + 1;
                while (j < n) {
                    if (s.charAt(j) == '(') cnt++;
                    else if (s.charAt(j) == ')') cnt--;
                    if (cnt == 0) {
                        num = calca(s.substring(i + 1, j));
                        break;
                    }
                    j++;
                }
                i = j;
            }
            if (ch == '+' || ch == '-' || ch == '*' || i == n - 1) {
                resCur = getRes(resCur, sign, num);
                if (ch == '+' || ch == '-' || i == n - 1) {
                    res += resCur;
                    resCur = 0;
                }
                sign = ch;
                num = 0;
            }
            i++;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            System.out.println(calca(s));
        }
    }
}

def getRes(resSofar, sign, num):
    if sign == "+":
        return resSofar + num
    elif sign == "-":
        return resSofar - num
    else:
        return resSofar * num

def calca(s):
    sign = "+"
    num = 0
    resCur = 0
    res = 0
    n = len(s)
    i = 0
    while i < n:
        ch = s[i]
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "(":
            cnt = 1
            j = i + 1
            while j < n:
                if s[j] == "(":
                    cnt += 1
                elif s[j] == ")":
                    cnt -= 1
                if cnt == 0:
                    num = calca(s[i + 1:j])
                    break
                j += 1
            i = j
        if ch in "+-*" or i == n - 1:
            resCur = getRes(resCur, sign, num)
            if ch in "+-" or i == n - 1:
                res += resCur
                resCur = 0
            sign = ch
            num = 0
        i += 1
    return res

s = input()
print(calca(s))

算法及复杂度

  • 算法：递归
  • 时间复杂度：，其中 是表达式的长度
  • 空间复杂度：，用于存储递归调用栈