【題目鏈接】

ybt 1331：【例1-2】后綴表達式的值

【題目考點】

1. 表達式求值

2. 表達式樹

表達式樹：一棵表達式樹可以表示一系列的運算。
表達式樹中的結點包括運算符與數值

struct Node {char c;//運算符int n;//數值 }

• 分支結點：c:運算符，n:該子樹對應的表達式的值
• 葉子結點：c:'\0'，n:數值
  表達式樹的值，是左子樹的值和右子樹的值，經過根結點運算符運算后得到的結果。

【解題思路】

題目中說參與運算的整數及結果的絕對值均在$2^{64}$范圍內，意思指的就是數據類型要設為long long。
（雖說$2^{6}3$及更大的數字不能用long long正確表示，但題目中實際上沒有這么大的數字，用long long即可。）

解法1：后綴表達式直接求值

從左向右掃描后綴表達式。

遇到數字時，將數字入棧。

遇到運算符時，彈出棧頂的兩個數，用該運算符對它們做相應的計算，結果入棧。

掃描結束后，棧頂數字就是結果。

解法2：后綴表達式構造表達式樹

如果讀到數字，那么新建數字結點入棧。

如果讀到運算符，則新建運算符結點np，出棧兩個結點，將這兩個結點的值通過np的運算符運算后得到的值存為新結點np的值，將np入棧。

讀完整個后綴表達式，棧中應該只剩1個結點，該結點就是表達式樹的根結點，該結點的值就是表達式的值 。

解法3：遞歸

先將字符串處理為由結構體對象構成的后綴表達式，每個結構體對象可能是數字可能是運算符。
后綴表達式的結構為：<第一個運算單元><第二個運算單元><運算符>
每個運算單元也許是一個數字，也許是一個后綴表達式。
后綴表達式數組最后一個元素的下標為p。
設函數solve()，求從第p位置開始向左遍歷取到的第一個運算單元的值。每取一個元素，p向左移動一個位置。

• 如果p位置是數字，直接返回這個數字的值。
• 如果p位置是運算符，那么從p位置開始向左取兩個運算單元的值，并用當前位置的運算符進行計算，得到這一運算單元的值。

【題解代碼】

解法1：后綴表達式直接求值

#include <bits/stdc++.h> using namespace std; typedef long long LL;//用LL代替long long stack<LL> stk; LL calc(LL a, LL b, char c)//數字a，b和運算符c，運算后的值 {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;} } int main() {char s[260];//讀入整個字符串 LL num = 0;//保存分解出來的數字 cin.getline(s, 260);for(int i = 0; s[i] != '@'; ++i)//遍歷字符串 {if(s[i] >= '0' && s[i] <= '9')//如果是數字字符，則構造數字num num = num * 10 + (s[i] - '0');else if(s[i] == ' ')//如果遇到空格，完成數字num的構造，將num壓棧 {stk.push(num);num = 0;}else//如遇到運算符，出棧兩個數，進行計算 {LL b = stk.top();//第二個運算數 stk.pop();LL a = stk.top();//第一個運算數 stk.pop();stk.push(calc(a, b, s[i]));}}cout << stk.top();//最后棧中剩下的數字，就是最后的結果。出棧并輸出它。 return 0; }

解法2：后綴表達式構造表達式樹

#include <bits/stdc++.h> using namespace std; typedef long long LL;//用LL代替long long struct Node {char c;//運算符 LL n;//數字int left, right; }; Node node[300]; int p;//node數組的下標 stack<int> stk; LL calc(LL a, LL b, char c)//數字a，b和運算符c，運算后的值 {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;} } int main() {char s[260];//讀入整個字符串 LL num = 0;//保存分解出來的數字 cin.getline(s, 260);for(int i = 0; s[i] != '@'; ++i)//遍歷字符串 {if(s[i] >= '0' && s[i] <= '9')//如果是數字字符，則構造數字num num = num * 10 + (s[i] - '0');else if(s[i] == ' ')//如果遇到空格，完成數字num的構造，將數字結點壓棧 {node[++p].n = num;stk.push(p);num = 0;}else//如遇到運算符，新建運算符結點，出棧兩個結點，作為運算符結點的子樹 {int pb = stk.top();//第二個運算數結點地址 stk.pop();int pa = stk.top();//第一個運算數結點地址 stk.pop();node[++p].c = s[i];node[p].n = calc(node[pa].n, node[pb].n, node[p].c);node[p].left = pa, node[p].right = pb;//設左右子樹 stk.push(p);//將新的運算符結點的地址入棧 }}int root = stk.top();//最后棧中剩下的是表達式樹根結點的地址cout << node[root].n;//根結點的值就是整個表達式樹的值 return 0; }

解法3：遞歸

#include <bits/stdc++.h> using namespace std; typedef long long LL;//用LL代替long long struct Node {char c;//運算符 LL n;//數字 }; Node eq[300];//轉化后的后綴表達式 int p;//node數組的下標 stack<int> stk; LL calc(LL a, LL b, char c)//數字a，b和運算符c，運算后的值 {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;} } LL solve()//如果node[p]是數字，返回該數字。如果node[p]是運算符，返回以第p位置為運算符的后綴表達式的值 {int e = p--;if(eq[e].c == '\0')//如果是數字 return eq[e].n;else//如果是運算符 {LL b = solve();LL a = solve();return calc(a, b, eq[e].c);} } int main() {char s[260];//讀入整個字符串 LL num = 0;//num:保存分解出來的數字cin.getline(s, 260);for(int i = 0; s[i] != '@'; ++i)//遍歷字符串 {if(s[i] >= '0' && s[i] <= '9')//如果是數字字符，則構造數字num num = num * 10 + (s[i] - '0');else if(s[i] == ' ')//如果遇到空格，完成數字num的構造{eq[++p].n = num;num = 0; }else//如遇到運算符 eq[++p].c = s[i];}//此時p指向最后一個位置 cout << solve();return 0; } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1331：【例1-2】后缀表达式的值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。