表达式求值（两种方法：栈或递归）-摩杜云开发者社区

描述

Dr.Kong设计的机器人卡多掌握了加减法运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20 ，add(10,98) 的值是108等等。经过训练，Dr.Kong设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。

假设表达式可以简单定义为:

1. 一个正的十进制数 x 是一个表达式。

2. 如果 x 和 y 是表达式，则函数min(x,y )也是表达式,其值为x,y 中的最小数。

3. 如果 x 和 y 是表达式，则函数max(x,y )也是表达式,其值为x,y 中的最大数。

4．如果 x 和 y 是表达式，则函数add(x,y )也是表达式,其值为x,y 之和。

例如，表达式 max(add(1,2),7) 的值为 7。

请你编写程序，对于给定的一组表达式，帮助 Dr.Kong 算出正确答案，以便校对卡多计算的正误。

输入

第一行： N 表示要计算的表达式个数（1≤ N ≤ 10）
接下来有N行，每行是一个字符串，表示待求值的表达式
（表达式中不会有多余的空格，每行不超过300个字符，表达式中出现的十进制数都不
超过1000。）

输出

输出有N行，每一行对应一个表达式的值。

样例输入

3add(1,2) max(1,999) add(min(1,1000),add(100,99))

样例输出

两种方法：

第一种用单调栈，注释挺详细就不写思路了。

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

const int N = 310;

stack <int> op;
// 存储add, max, min 这些运算符
// add = -1, max = -2, min = -3
stack <int> number;
// 存储整数

char a[N];

int main()
{
    int T;
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> a;
        int len =strlen(a); // len 字符串a 的长度
        for(int i=0; i<len; i++) {
            if(a[i] == ')') // 找到 ')' 前面为目前的最小项
            { // 把最小项转换成数值入栈
                int optemp = op.top();
                op.pop();
                int x = number.top();
                number.pop();
                int y = number.top();
                number.pop();

                if(optemp == -1)
                    number.push(x+y);
                else if(optemp == -2)
                    number.push(max(x,y));
                else
                    number.push(min(x,y));
            }
            else if(a[i] == 'a' && a[i+1] == 'd') // 找到add, op 入栈 -1
                op.push( -1 );
            else if(a[i] == 'm' && a[i+1] == 'a') // 找到max, op 入栈 -2
                op.push( -2 );
            else if(a[i] == 'm' && a[i+1] == 'i') // 找到min, op 入栈 -3
                op.push( -3 );
            else if(isdigit(a[i])) { // 找到数字，求他的值，入栈到 number
                int temp = 0;
               while(isdigit(a[i])) {
                    temp = temp*10 + a[i]-'0';
                    i++;
               }
               i--;
               number.push(temp);
            }
        }
        cout << number.top() << endl;
        number.pop();
    }
    return 0;
}

第二种是递归：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 350;

char a[N];

int todigit(int s, int e) {
    int temp = 0;
    for(int i=s; i<=e; i++) {
        temp = temp*10 + a[i]-'0';
    }
    return temp;
}

int work(int s, int e) {
    if(isdigit(a[s])) { // 如果以数字开头转化其为整数值
        int i = s;
        while(isdigit(a[i])) i++;
        int number = todigit(s, i-1);
        return number;
    }

    int op = 0; // op = 1 Ϊ add, 2 Ϊ max , 3 Ϊ min

    if(a[s] == 'a' && a[s+1] == 'd') {
        op = 1;
    }

    if(a[s] == 'm' && a[s+1] == 'a') {
        op = 2;
    }
    if(a[s] == 'm' && a[s+1] == 'i') {
        op = 3;
    }
    if(op != 0)
     s += 4;
    int mid = s; 
    
    // 找到当前操作的分界
    // 例如 max(a , b)中 ',' 就是分界 
    // 找到分界后，分别去求 a、 b 的值
    if(isdigit(a[mid])) {  
        for(int i=s; i<=e; i++) {
            if(a[i] == ','){
                mid = i;
                break;
            }
        }
    }
    else {
       int lk = -1, rk = -1;
       while(lk != rk || lk == -1) {
           if(a[mid] == '(')
              lk ++;
           if(a[mid] == ')')
              rk ++;
           mid ++;
         }
    }

    int ans1, ans2;
    if(a[e] == ')')
        e--;

    ans1 = work(s, mid-1);
    ans2 = work(mid+1, e);

    if(op == 1)
        return ans1+ans2;
    if(op == 2)
        return max(ans1, ans2);
    if(op == 3)
        return min(ans1, ans2);
}

int main()
{
    int T;
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> a;
        int len = strlen(a);
        cout << work(0, len-1) << endl;
    }
    return 0;
}