NYOJ 305

╰+攻爆jí腚メ 2022-06-17 10:29 116阅读 0赞

## 表达式求值 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 3

描述

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行，每一行对应一个表达式的值。

样例输入

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

样例输出

3
    999
    200

第一种方法栈处理，模拟。

#include<bits/stdc++.h>
    using namespace std;
    char fun(char a,char b)
    {
        if(a=='a')
            return '+';
        else if(a=='m'&&b=='a')
            return '>';
        else
            return '<';
    }
    int fun2(int a,int b,char c)
    {
        switch(c)
        {
            case '+':return a+b;
            case '<':return min(a,b);
            case '>':return max(a,b);
        }
    }
    int main()
    {
        int n,len,tempnum,a,b,wei;
        char str[400],tempchar,cal;
        stack<char>ope;
        stack<int>num;
        scanf("%d",&n);
        getchar();
        while(n--)
        {
    
            gets(str);
            len=strlen(str);
            for(int i=0;i<len;i++)
            {
                if(str[i]=='a'||str[i]=='m')
                {
                    tempchar = fun(str[i],str[i+1]);
                    ope.push(tempchar);
                    i=i+2;
                }
                else if(str[i]>='0'&&str[i]<='9')
                {
                    sscanf(&str[i],"%d%n",&tempnum,&wei);
                    i=i+wei-1;
                    num.push(tempnum);
                }
                else if(str[i]==')')
                {
                    b=num.top();num.pop();
                    a=num.top();num.pop();
                    cal=ope.top();ope.pop();
                    num.push(fun2(a,b,cal));
                }
            }
            printf("%d\n",num.top());
        }
        return 0;
    }

别人的方法

第二种方法递归自我感觉比较有意思（[点此跳转][Link 1]）

#include <stdio.h>
    #include <string.h>
    char str[301];
    int start;
    int max(int a, int b)
    {
        return a > b ? a : b;
    }
    
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    int val()
    {
        int v, n;
        switch(str[start])
        {
        case 'm':
            start += 4;
            if(str[start - 2] == 'n') return min(val(), val());
            else return max(val(), val());
        case 'a':
            start += 4;
            return val() + val();
        case ',':
        case ')':
            ++start;
            return val();
        default:
            sscanf(str + start, "%d%n", &v, &n);
            start += n;
            return v;
        }
    }
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            scanf("%s", str);
            start = 0;
            printf("%d\n", val());
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/chang_mu/article/details/19483529