【表達式轉換 (25 分)】
- 2019 年 10 月 10 日
- 筆記
題目分析
首先規定優先順序，括弧為最高優先順序，乘號或除號為次優先順序，加或減號為最低優先順序，至於數字，碰到就直接輸出即可。 既然是數字，就有小數，整數，正數，負數之分，還有關於二元運算符的輸出，在括弧內的二元運算符優先輸出，優先順序高的優先輸出（當然括弧不算啊） 根據題意，在輸出時可分為以下幾種情況。
- (+1……
- +1…… 對於正號，是不能輸出的
- -1……
- 3
- 34…
- 3.4… （注意：上面的…指一堆未知長度的數字）
- 碰到 ）符號，將與它對應的括弧這之間的符號從棧內導出，也就是輸出它們。 上面幾種情況只討論了部分輸出問題，下面討論向棧中插入二元運算符。
- 當棧為空或者棧頂運算符的優先順序小於當前二元運算符的優先順序時，將該二元運算符導入。
- 倘若棧頂運算符的優先順序大於或等於當前二元運算符的優先順序，又分為以下兩種情況，1.若棧頂運算符為（ 符號，則直接將該運算符插入即可； 2.若棧頂運算符不是（ 符號，則優先輸出棧內的元素,直到碰到（ 符號或者棧為空，然後將當前二元運算符插入。
正確程式碼
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<stack> #include<queue> #include<map> using namespace std; stack<char> sign; char s[22]; map<char, int> mp; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); mp['+'] = mp['-'] = 1; mp['*'] = mp['/'] = 2; mp['('] = mp[')'] = 3; scanf("%s", s); int len = strlen(s); bool isfirst = true; for(int i = 0; i < len; i++) { if((!i || (i && s[i-1] == '(')) && (s[i] == '+' || s[i] == '-')) { if(!isfirst) printf(" "); if(s[i] != '+') printf("%c",s[i]); while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9'))) { ++i; printf("%c", s[i]); } if(isfirst) isfirst = false; } else if(s[i] >= '0' && s[i] <= '9') { if(!isfirst) printf(" "); printf("%c", s[i]); while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9'))) { ++i; printf("%c", s[i]); } if(isfirst) isfirst = false; } else if(s[i] == ')') { while(!sign.empty() && sign.top() != '(') { printf(" %c", sign.top()); sign.pop(); } if(!sign.empty() && sign.top() == '(') sign.pop(); } else if(sign.empty() || (mp[s[i]] > mp[sign.top()])) sign.push(s[i]); else { while(!sign.empty() && sign.top() != '(') { printf(" %c", sign.top()); sign.pop(); } sign.push(s[i]); } } while(!sign.empty()) { printf(" %c", sign.top()); sign.pop(); } }
擴展
關於這道題，如果讓你輸出這個表達式的值，可以這樣做。 安排兩個棧，分別存數字和符號，具體要求如下。（該程式還有欠缺，目前對帶正號的正數以及小數不支援，只支援正常的整數混合運算）
#include<iostream> #include<stack> #include<cstdio> #include<cstring> #include<map> using namespace std; stack<int> num; stack<char> oper; map<char, int> mp; char s[22]; void solve(int a, int b, char o) { int c; if(o == '+') c = a + b; else if(o == '-') c = a - b; else if(o == '*') c = a * b; else if(o == '/') c = a / b; if(o != ')') num.push(c); } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%s", &s); int len = strlen(s); mp['('] = mp[')'] = 0; mp['+'] = mp['-'] = 1; mp['*'] = mp['/'] = 2; for(int i = 0; i < len; i++) { if(s[i] >= '0' && s[i] <= '9') num.push(s[i] - '0'); else { if(oper.empty() || mp[oper.top()] < mp[s[i]] || s[i] == '(') oper.push(s[i]); else { if(mp[oper.top()] == mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); oper.push(s[i]); } else if(mp[oper.top()] > mp[s[i]]) { if(s[i] == ')') { while(!oper.empty() && mp[oper.top()] > mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } if(oper.top() == '(') oper.pop(); } else { while(!oper.empty() && mp[oper.top()] >= mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } oper.push(s[i]); } } } } } while(!oper.empty()) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } cout << num.top() << endl; }
