题解 | #表达式求值# 基于递归的详细注释

#include <iostream>
#include <stack>
using namespace std;
// 全局变量用于统计递归函数对输入字符串的操作，作为已操作过的下标来使用
int pos;

// 递归函数是计算的一部分，自然需要返回计算结果：int
// 为了节省栈空间，这里采用“引用”的方式。
int result(const string& data){
    // 递归中的概念有：数字，计算符号，计算顺序，结果。前三者对一个下面3个数据结构。
    // 他们的逻辑关系就是 “符号” + “数字”（按照顺序） 最终得到结果   
    int num = 0;
    // 针对第一个数字的计算逻辑是‘+’
    char flag = '+';
    stack<int> stk;
    int len = data.length();
    // pos作为下标，当期小于长度的时候就完成了整个字符串的遍历
    while(pos < len){
        if(data[pos] == '('){
            // 遇见'('触发迭代
            // 此处一定要想先对pos做更改
            pos++;
            // 将子问题的结果用到本问题的计算中去，即递归之间的逻辑。 
            num = result(data);
        }
        // 本层递归的逻辑处理
        // 数字
        while(pos < len && isdigit(data[pos])){
            num = 10*num + data[pos++] - '0';
        }
        // 符号以及运算顺序
        switch (flag) {
            case '+':
            {
                // 顺序的具体体现：
                stk.push(num);
                break;
            }
            case '-':
            {
                stk.push(-num);
                break;     
            }
            case '*':
            {
                // 顺序的具体体现：
                stk.top() *= num;
                break;
            }
            case '/':
            {
                stk.top() /= num;
                break;  
            }
        }
        // 完成一次更新逻辑，初始化数据进行下一次更新。即更新符号和数字。
        num = 0;
        flag = data[pos];
        // 子问题的嵌套处理
        if(flag == ')'){
            pos++;
            break;
        }
        pos++;
    }
    int sum = 0;
    while(!stk.empty()){
        sum += stk.top();
        stk.pop();
    }
    return sum;
}

int main() {
    string s;
    getline(cin,s);
    pos = 0;
    cout << result(s) <<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")