程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ305 表達式求值(遞歸or棧)

NYOJ305 表達式求值(遞歸or棧)

編輯：C++入門知識

NYOJ305 表達式求值(遞歸or棧)

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

題目分析：
以前做類似的題目，都是用到棧的應用，這裡是參考大神的代碼給出的遞歸代碼，很簡單，遍歷字符串，如果遇到‘d’，那麼應該是add()，如果遇到‘x’，是max()，如果遇到‘n’，是min()，
需要注意的是無論是關鍵字符還是衛星字符，都要是下標自增，這裡的主要技巧是遞歸，個人認為這個函數用的很巧妙，自己也知道這個函數 sscanf(str+first,”%d%n”,&x,&n);，從沒有這麼用過，受教了。。。

AC代碼：

/**
  *@xiaoran
  *遞歸
  */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
char str[1005];
int first;
int Opera(){
    int n,x;
    switch(str[first]){
        case 'd':{
            ++first;
            if(str[first-2]=='d') return Opera()+Opera();
            else return Opera();
        }
        case 'x': ++first; return max(Opera(),Opera());
        case 'n': ++first; return min(Opera(),Opera());

        case 'a':
        case 'm':
        case 'i':
        case '(':
        case ')':
        case ',': ++first; return Opera();

        default:{
            //將值寫入x，位數寫入n
            sscanf(str+first,%d%n,&x,&n);
            first+=n; return x;
        }
    }

}

int main()
{
    int n;
    scanf(%d,&n);
    while(n--){
        scanf(%s,str);
        first=0;
        int res=Opera();
        printf(%d
,res);

    }
    return 0;
}