题解 | #四则运算#

#include <stdio.h>
#include <string.h>

// 1.无括号 用栈先乘除后加减
// 遇到+-继续入栈,遇到*/出栈1个,和新元素计算后入栈
// 2.有括号 左括号开始递归1步骤,右括号出递归结果 入栈
//注意遇到括号内有负号先要变号再入栈
int i;
int compute(char *data);
int main()
{
    
    char str[1000];
    scanf("%s", str);
    i=0;
    int res = compute(str);
    printf("%d", res);

    return 0;
}

int compute(char *data)
{
    int stack[1000];
    int top = -1;
    int len = strlen(data);
    char flag = '+';//默认为+
    while (i <=len)
    {
        int num = 0;
        if(data[i]=='-'){
            flag = '-';
            i++;
        }
        
        if (data[i] == '{' || data[i] == '[' || data[i] == '(')
        {
            i++;
            num = compute(data);
        }
        //获取数字
        while (data[i] - '0' >= 0 && data[i] - '0'<=9)
        {
            num = num * 10 + data[i] - '0';
            i++;
        }
        //数字前面的符号
        switch(flag)
        {
        case '+':
            stack[++top] = num;
            break;
        case '-':
            stack[++top] = -num;
            break;
        case '*'://由于第一个不可能是*，所以栈顶元素可以直接乘
            stack[top] *= num;
            break;
        case '/':
            stack[top] /= num;
            break;
        }
        flag = data[i];//i已经指向下一个符号
        if (data[i] == '}' || data[i] == ']' || data[i] == ')')
        {
            i++;
            break;//跳出函数，并在循环体外计算栈顶
        }
        i++;
    }

    int ret = 0;
    //这个函数中累计了top个整数，结束之后就返回结果，直到计算到最后一个数
    //每一次top需要归零，用于递归
    for (int j = 0; j <= top; j++)
    {
        ret += stack[j];
    }

    return ret;
}

其实这道题简单中也有，只不过没有那么多括号，总结一下就是控制栈的push和pop。

在这道题中，+和-是push，*和/是和top相运算后再把结果push。

左括号是进入递归，右括号是跳出递归，由于有递归，所以每次递归会重新开一个栈，每次跳出递归就是把栈里面所有的数

相加pop出来即可。