【題目鏈接】

ybt 1358：中綴表達式值(expr)

【題目考點】

1. 表達式求值

• 中綴表達式轉(zhuǎn)后綴表達式
• 后綴表達式求值

【解題思路】

由于題目要求做中綴表達式轉(zhuǎn)為后綴表達式，而后求值。那么這里就不給出其他求值方法了。

1. 先判斷表達式是否合法

括號匹配：掃描整個算式，遇到左括號就入棧，遇到右括號，就出棧一次。在這一過程中，如果棧空了，還遇到右括號，那么表達式非法。

對于負號：行首的負號，以及'('后的負號，前面插入'0'

第一個字符不可以是運算符，除了'('。最后一個字符不可以是運算符，除了')'

檢查是否有連續(xù)出現(xiàn)的運算符()±@
如果連續(xù)兩個字符是運算符：

如果兩個字符是")("，那么是非法的。

除了上述情況，如果第一個是')'，或第二個是'('，那么是合法的。

其余兩個連續(xù)運算符出現(xiàn)的情況全是非法的

2. 中綴表達式轉(zhuǎn)后綴表達式

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

遇到數(shù)字時，將數(shù)字添加到后綴表達式

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

掃描結束后若棧中有運算符，都出棧，加入后綴表達式。
可以預先在字符串末尾加上一個優(yōu)先級最低的')'，以促使運算符棧中的運算符都出棧。

3. 求解后綴表達式

后綴表達式的求解方法見：信息學奧賽一本通 1331：【例1-2】后綴表達式的值

【題解代碼】

解法1：中綴表達式轉(zhuǎn)為后綴表達式，而后求值。

#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的運算符的優(yōu)先級 string s;//中綴表達式字符串 void initPri() {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;} } bool isCalc(char c)//判斷c是否是運算符 {return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')'; } bool isValid()//判斷s是否是合法的中綴表達式 {//1.檢查括號匹配 stack<char> stk;for(int i = 0; i < s.length(); ++i) {if(s[i] == '(')stk.push(s[i]);else if(s[i] == ')'){if(stk.empty())return false;elsestk.pop();}}if(stk.empty() == false)return false;//2.單獨的負號前加0 for(int i = 0; i < s.length(); ++i){if(i == 0 && s[i] == '-')s = '0' + s;//前面加0else if(s[i] == '-' && s[i-1] == '(')//右括號后面的負號s.insert(i, "0");//在第i位置插入0 }//3. 除了首位的'('與末尾的')'，其余情況首尾不能為運算符if(isCalc(s[0]) && s[0] != '(')return false;int ed = s.length()-1;//末尾位置下標 if(isCalc(s[ed]) && s[ed] != ')')return false;//4.判斷是否有連續(xù)的不合法的運算符for(int i = 0; i < s.length()-1; ++i){if(isCalc(s[i]) && isCalc(s[i+1]))//如果有相鄰兩個運算符{if(s[i] == ')' && s[i+1] == '(')return false;else if(!(s[i] == ')' || s[i+1] == '('))//如果第一個是`')'`，或第二個是`'('`，那么是合法的。其余是非法的。 return false;} } return true; } 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數(shù)組 int n, num = 0;cin >> s;if(isValid() == false){cout << "NO";return 0;}s += ')';//取巧，把一個優(yōu)先級最低的符號')'加到字符串末尾，促使運算符都出棧，以完成最后的計算。 stack<char> cStk;//運算符棧 bool isFormingNum = false;//標志位 表示是否正在構造數(shù)字 for(int i = 0; i < s.length(); ++i)//最后一次取到人為添加的')' {if(s[i] >= '0' && s[i] <= '9')//如果掃描到數(shù)字 {isFormingNum = true;num = num * 10 + s[i] - '0';//將字符串轉(zhuǎn)化為數(shù) }else//如果掃描到運算符 {if(isFormingNum)//如果正在構造數(shù)字 {eq[++p].n = num;//將構造好的數(shù)字加入后綴表達式 num = 0;//保存數(shù)字的變量復原isFormingNum = false;}while(!(cStk.empty() || pri[s[i]] > pri[cStk.top()] || cStk.top() == '('))//入棧條件：棧空或要入棧的運算符比棧頂?shù)膬?yōu)先級更高或棧頂為左括號。入棧條件取反就是出棧條件。 {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; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1358：中缀表达式值(expr)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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