表達式求值

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

假設(shè)表達式定義為: 1. 一個十進制的正整數(shù) X 是一個表達式。 2. 如果 X 和 Y 是 表達式，則 X+Y, X*Y 也是表達式; *優(yōu)先級高于+. 3. 如果 X 和 Y 是 表達式，則 函數(shù) Smax(X,Y)也是表達式,其值為:先分別求出 X ,Y 值的各位數(shù)字之和，再從中選最大數(shù)。 4．如果 X 是 表達式，則 （X）也是表達式。 例如: 表達式 12*(2+3)+Smax(333,220+280) 的值為 69。 請你編程，對給定的表達式，輸出其值。 ? 輸入

【標準輸入】 第一行： T 表示要計算的表達式個數(shù) （1≤ T ≤ 10） 接下來有 T 行， 每行是一個字符串，表示待求的表達式，長度<=1000

輸出

【標準輸出】 對于每個表達式，輸出一行，表示對應(yīng)表達式的值。

樣例輸入

3 12+2*3 12*(2+3) 12*(2+3)+Smax(333,220+280)

樣例輸出

18 60 69

解題思路：這個求值的過程就是中綴式轉(zhuǎn)成后綴式的過程。

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<stack> using namespace std;const int maxn = 1005; int n; //表示串的長度 char str[maxn]; stack<int> s1; stack<char> s2; int getNum(int L,int R) {int num = 0;for(int i = L; i <= R; i++)num = num * 10 + str[i] - '0';return num; }int Calc(char op,int a,int b) {if(op == '+') return a + b;else if(op == '*') return a * b;else {int tmpa = 0, tmpb = 0;while(a > 0) {tmpa += a % 10;a /= 10;}while(b > 0) {tmpb += b % 10;b /= 10;}return max(tmpa,tmpb);} }int process() //將中綴式轉(zhuǎn)化為后綴式 {int a,b;char c;while(!s1.empty()) s1.pop();while(!s2.empty()) s2.pop();s2.push('#');for(int i = 0; i < n; i++) {if(str[i] == 'S' || str[i] == 'm' || str[i] == 'a' || str[i] == 'x') continue;if(str[i] == '(')s2.push(str[i]);else if(str[i] == ')') {c = s2.top();while(c != '(') {a = s1.top(); s1.pop();b = s1.top(); s1.pop();s1.push(Calc(c,a,b));s2.pop();c = s2.top();}s2.pop();}else if(str[i] >= '0' && str[i] <= '9') {int j = i;while(str[j] >= '0' && str[j] <= '9' && j < n) j++;j--;s1.push(getNum(i,j));i = j;}else if(str[i] == '+') {c = s2.top();while(c == '*' || c == '+') {a = s1.top(); s1.pop();b = s1.top(); s1.pop();s1.push(Calc(c,a,b));s2.pop();c = s2.top();}s2.push('+');}else if(str[i] == '*') {c = s2.top();while(c == '*') {a = s1.top(); s1.pop();b = s1.top(); s1.pop();s1.push(Calc(c,a,b));s2.pop();c = s2.top();}s2.push('*');}else if(str[i] == ',') s2.push(str[i]);}while(s2.top() != '#') {c = s2.top();s2.pop();a = s1.top(); s1.pop();b = s1.top(); s1.pop();s1.push(Calc(c,a,b));if(c == '+'){int p = 1;}}return s1.top(); }int main() {int t;scanf("%d",&t);while(t--){scanf("%s",str);n = strlen(str);printf("%d\n",process());}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的nyoj 1272 表达式求值(中缀式转后缀式)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。