【題目鏈接】

ybt 1356：計算(calc)

【題目考點】

1. 表達式求值

中綴表達式求值

2. 表達式樹

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

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

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

【解題思路】

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

設數字棧、運算符棧。設數組表示運算符優先級，其中'('優先級最高，')'優先級最低。
從左向右掃描表達式字符串：

遇到數字時，入數字棧。

遇到運算符時，入棧條件為：?？?#xff0c;或該運算符優先級比棧頂運算符優先級高，或者棧頂是'('。只有不滿足該條件，則一直出棧。
運算符出棧后，數字棧出棧兩個數字，加上剛剛出棧的運算符進行一次運算，將運算結果加入數字棧。
如果要入棧的是')'且棧頂是'('，那么二者配對，出棧運算符。否則運算符入棧。

掃描結束后若棧中有運算符，都出棧。

最后數字棧中的數字即為整個中綴表達式的運算結果
可以預先在字符串末尾加上一個優先級最低的')'，以促使運算符棧中的運算符都出棧。

解法2：中綴表達式轉為后綴表達式，而后求值。

中綴表達式轉后綴表達式：

設數組保存后綴表達式，設運算符棧。
從左向右掃描表達式字符串：

遇到數字時，將數字添加到后綴表達式

遇到運算符時，入棧條件為：?？?#xff0c;或該運算符優先級比棧頂運算符優先級高，或者棧頂是'('。只有不滿足該條件，則一直出棧。出棧的運算符添加到后綴表達式。

掃描結束后若棧中有運算符，都出棧，加入后綴表達式。
可以預先在字符串末尾加上一個優先級最低的')'，以促使運算符棧中的運算符都出棧。
而后求解后綴表達式，后綴表達式的求解方法見：信息學奧賽一本通 1331：【例1-2】后綴表達式的值

解法3：建立表達式樹

設數字棧、運算符棧。設數組表示運算符優先級，其中'('優先級最高，')'優先級最低。
從左向右掃描表達式字符串：

遇到數字時，入數字棧。

遇到運算符時，入棧條件為：?？?#xff0c;或該運算符優先級比棧頂運算符優先級高，或者棧頂是'('。只有不滿足該條件，則一直出棧。
運算符出棧后，數字棧出棧兩個數字，加上剛剛出棧的運算符進行一次運算，將運算結果加入數字棧。
如果要入棧的是')'且棧頂是'('，那么二者配對，出棧運算符。否則運算符入棧。

掃描結束后若棧中有運算符，都出棧。

最后數字棧中的數字即為整個中綴表達式的運算結果
可以預先在字符串末尾加上一個優先級最低的')'，以促使運算符棧中的運算符都出棧。

【題解代碼】

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

#include<bits/stdc++.h> using namespace std; #define N 1005 int pri[128];//pri[i]:ascii碼為i的運算符的優先級 void initPri() {pri['('] = 5;pri['^'] = 4;pri['*'] = pri['/'] = 3;pri['+'] = pri['-'] = 2;pri[')'] = 1; } int calc(int a, int b, char c) {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;case '^':return (int)pow(a,b);} } int main() {initPri();//初始化pri數組 int n, num = 0;char s[N];cin >> s;//假設輸入的是合法的表達式 int len = strlen(s);s[len] = ')';//取巧，把一個優先級最低的符號')'加到字符串末尾，促使運算符都出棧，以完成最后的計算。 stack<int> nStk;//數字棧 stack<char> cStk;//運算符棧 bool isFormingNum = false;//標志位 表示是否正在構造數字 for(int i = 0; i <= len; ++i)//最后一次取到人為添加的')' {if(s[i] >= '0' && s[i] <= '9')//如果掃描到數字 {isFormingNum = true;num = num * 10 + s[i] - '0';//將字符串轉化為數 }else//如果掃描到運算符 {if(isFormingNum)//如果正在構造數字 {nStk.push(num);//將構造好的數字壓入數字棧 num = 0;//保存數字的變量復原isFormingNum = false;}while(!(cStk.empty() || pri[s[i]] > pri[cStk.top()] || cStk.top() == '('))//入棧條件：?？栈蛞霔５倪\算符比棧頂的優先級更高或棧頂為左括號。入棧條件取反就是出棧條件。 {int b = nStk.top(); nStk.pop();int a = nStk.top(); nStk.pop();char c = cStk.top(); cStk.pop();nStk.push(calc(a, b, c));}if(cStk.empty() == false && cStk.top() == '(' && s[i] == ')')//如果左右括號配對 cStk.pop();//彈出左括號 不壓棧 else cStk.push(s[i]);//運算符壓棧 }}cout << nStk.top();//最后棧頂的值就是算式的結果 return 0; }

解法2：中綴表達式轉為后綴表達式，而后求值。

#include<bits/stdc++.h> using namespace std; #define N 1005 struct Node {int n;char c; }; Node eq[N];//保存后綴表達式 int p; int pri[128];//pri[i]:ascii碼為i的運算符的優先級 void initPri() {pri['('] = 5;pri['^'] = 4;pri['*'] = pri['/'] = 3;pri['+'] = pri['-'] = 2;pri[')'] = 1; } int calc(int a, int b, char c) {switch(c){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;case '^':return (int)pow(a,b);} } int solve()//遞歸求解后綴表達式 {int i = p--;if(eq[i].c){int b = solve(); int a = solve();return calc(a, b, eq[i].c);}elsereturn eq[i].n; } int main() {initPri();//初始化pri數組 int n, num = 0;char s[N];cin >> s;//假設輸入的是合法的表達式 int len = strlen(s);s[len] = ')';//取巧，把一個優先級最低的符號')'加到字符串末尾，促使運算符都出棧，以完成最后的計算。 stack<char> cStk;//運算符棧 bool isFormingNum = false;//標志位 表示是否正在構造數字 for(int i = 0; i <= len; ++i)//最后一次取到人為添加的')' {if(s[i] >= '0' && s[i] <= '9')//如果掃描到數字 {isFormingNum = true;num = num * 10 + s[i] - '0';//將字符串轉化為數 }else//如果掃描到運算符 {if(isFormingNum)//如果正在構造數字 {eq[++p].n = num;//將構造好的數字加入后綴表達式 num = 0;//保存數字的變量復原isFormingNum = false;}while(!(cStk.empty() || pri[s[i]] > pri[cStk.top()] || cStk.top() == '('))//入棧條件：?？栈蛞霔５倪\算符比棧頂的優先級更高或棧頂為左括號。入棧條件取反就是出棧條件。 {eq[++p].c = cStk.top(); cStk.pop();}if(cStk.empty() == false && cStk.top() == '(' && s[i] == ')')//如果左右括號配對 cStk.pop();//彈出左括號 不壓棧 else cStk.push(s[i]);//運算符壓棧 }}cout << solve();//求后綴表達式eq的值 return 0; }

解法3：建立表達式樹

#include<bits/stdc++.h> using namespace std; #define N 1005 struct Node {int val;//數值 char calc;//運算符 int left, right; }; Node node[N]; int p, num; int pri[128]; stack<int> nStk;//結點棧 stack<char> cStk;//運算符棧 void initPri() {pri['^'] = 5;pri['*'] = pri['/'] = 4;pri['+'] = pri['-'] = 3;pri['('] = 6;pri[')'] = 1; } int calc(int a, int b, char c) {switch(c){case '+':return a + b;case '-':return a - b;case '*':return a * b;case '/':return a / b;case '^':return (int)pow(a,b);} } int main() {initPri();string s;cin>>s;s += ')';int num = 0;bool isForming = false;for(int i = 0; i < s.length(); ++i){if(s[i] >= '0' && s[i] <= '9'){num = num * 10 + s[i] - '0'; isForming = true;}else{if(isForming){node[++p].val = num;nStk.push(p);num = 0;isForming = false;}while(!(cStk.empty() || pri[s[i]] > pri[cStk.top()] || cStk.top() == '(')){int pr = nStk.top(); nStk.pop();int pl = nStk.top(); nStk.pop();node[++p].calc = cStk.top(); cStk.pop(); node[p].left = pl, node[p].right = pr;node[p].val = calc(node[pl].val, node[pr].val, node[p].calc);nStk.push(p);}if(cStk.empty() == false && cStk.top() == '(' && s[i] == ')')cStk.pop();elsecStk.push(s[i]); }}int root = nStk.top();cout << node[root].val;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1356：计算(calc)的全部內容，希望文章能夠幫你解決所遇到的問題。

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