題目描述：
讀入一個只包含 + ，-，×， / 的非負整數計算運算式，計算該運算式的值，
輸入格式：
測驗輸入包含若干測驗用例，每個測驗用例占一行，每行不超過200個字符，整數和運草符之間用一個空格分隔，沒有非法運算式，當一行中只有0時輸入結束，相應的結果不要輸出，
輸出格式：
對每個測驗用例輸出1行，即該運算式的值，精確到小數點后2位，
樣例輸入：
30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
0
樣例輸出：
12178.21
思路
題目給出的是中綴運算式，所以要計算它的值主要是兩個步驟：（如果不懂什么是前綴運算式和后綴運算式請看：https://www.cnblogs.com/chensongxian/p/7059802.html和https://www.cnblogs.com/zzliu/p/10801113.html）
①中綴運算式轉后綴運算式，
②計算后綴運算式，
下面分別講一下這兩步，
步驟1：中綴運算式轉后綴運算式
①設立一個運算子堆疊，用以臨時存放運算子；設立一個陣列或者佇列，用以存放后綴表
達式，
②從左至右掃描中綴運算式，如果碰到運算元(注意：運算元可能不止一位，因此需要
一位一位讀入然后合并在一起，具體實作見代碼），就把運算元加入后綴運算式中，
③如果碰到運算子op，就將其優先級與運算子堆疊的堆疊頂運算子的優先級比較，
（1）若op的優先級高于堆疊頂運算子的優先級，則壓入運算子堆疊，
（2）若op的優先級低于或等于堆疊頂運算子的優先級，則將運算子堆疊的運算子不斷彈出到
后綴運算式中，直到op的優先級高于堆疊頂運算子的優先級，
④重復上述操作，直到中綴運算式掃描完畢，之后若運算子堆疊中仍有元素，則將它們依
次彈出至后綴運算式中，
（1）所謂運算子的優先級即它們計算的優先級，其中乘法 == 除法 > 加法==減法，在具體實
現上可以用map建立運算子和優先級的映射，優先級可以用數字表示，例如乘法和除法優先
級為1，加法和減法優先級為0，
（2）關于為什么當op高于堆疊頂時就壓入運算子堆疊，這里舉一個例子；
對中綴運算式3 + 2×5，顯然如果先計算加法3 + 2會引起錯誤，必須先計算乘法2×5，當
從左到右掃描時，加號先進入運算子堆疊，而由于乘號優先級大于加號，其必須先計算，因此
在后綴運算式中乘號必須在加號前面，于是在堆疊中乘號要比加號更靠近堆疊頂，以讓其先于加
號進入后綴運算式，
（3）關于為什么當op等于堆疊頂時不能直接壓入運算子堆疊，這里舉一個例子：
對中綴運算式2 / 3×4，如果設定優先級相等時直接壓入運算子堆疊，那么演算法步驟如下：
a)2進入后綴運算式，當前后綴運算式為2，
b) / 進入運算子堆疊，當前運算子堆疊為 /*，
c)3進入后綴運算式，當前后綴運算式為23，
d） * 與運算子堆疊的堆疊頂元素 / 比較，相等，壓入運算子堆疊，當前運算子堆疊為/，
e)4進入后綴運算式，當前后綴運算式為234，
f)中綴運算式掃描完畢，運算子堆疊非空，將其全部彈入后綴運算式，最終后綴運算式變
為234*/，
g)計算該后綴運算式，發現其實變成了2 / (3×4），顯然這跟原來中綴運算式的計算結果
完全不同，
（4）本題沒有出現括號，但是如果出現括號，處理方法也很簡單，遇到括號時：
，如果是左括號‘(’，就壓入運算子堆疊；如果是右括號‘）’，就把運算子堆疊里的元
素不斷彈出到后綴運算式直到碰到左括號‘(’ ，此時將這一對括號丟棄，
步驟2：計算后綴運算式
從左到右掃描后綴運算式，如果是運算元，就壓入堆疊；如果是運算子，就連續彈出兩個運算元(注意：后彈出的是第一運算元，先彈出的是第二運算元），然后進行運算子的操作，
生成的新運算元壓入堆疊中，反復直到后綴運算式掃描完畢，這時堆疊中只會存在一個數，就是最終的答案，
（1）注意除法可能導致浮點數，因此運算元型別要設成浮點型，
（2）題目中說肯定是合法運算式，因此上面操作一定能夠成功，但如果題目表明可能出現
非法運算式，那就要注意每一步使用的物件是否合法，
#include<iostream> #include<string> #include<stack> #include<fstream> #include<queue> #include<map> using namespace std; struct node { double num; char op; bool flag; }; string str; //中綴運算式 stack<node> s; //運算子堆疊 queue<node> q; //后綴運算式序列 map<char, int> oop; //運算子和優先級的映射 void change() { //將中綴運算式轉換為后綴運算式 node temp; for (int i = 0; i < str.length();) { if (str[i] >= '0' && str[i] <= '9') { temp.flag = true; temp.num = str[i++] - '0';//記錄這個運算元的第一個數位 while (i < str.length() && str[i] >= '0' && str[i] <= '9') { temp.num = temp.num * 10 + (str[i] - '0');//更新這個運算元 i++; } q.push(temp); } else { temp.flag = false; //只要運算子堆疊的堆疊頂元素比該運算子優先級高， //就把運算子堆疊頂元素彈出到后綴運算式的佇列中， while (!s.empty() && oop[str[i]] <= oop[s.top().op]) { q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp);//將運算子壓入堆疊， i++; } } while (!s.empty()) {//如果運算子堆疊中還有元素就把他彈出到后綴運算式佇列中， q.push(s.top()); s.pop(); } }
double cal() {//計算后綴運算式 double temp1, temp2; node cur, temp; while (!q.empty()) {//只要后綴運算式非空 cur = q.front();//cur記錄首元素 q.pop(); if (cur.flag == true) s.push(cur);//如果是數字直接入堆疊， else {//如果是運算子 temp2 = s.top().num;//彈出第二運算元 s.pop();， temp1 = s.top().num;//彈出第一運算元，第一運算元在運算子前面，即次頂元素在運算子的前面，這一點與前綴運算式不同， s.pop(); temp.flag = true; if (cur.op == '+') temp.num = temp1 + temp2;//做加法 else if (cur.op == '-') temp.num = temp1 - temp2;//做減法 else if (cur.op == '*') temp.num = temp1 * temp2;//做乘法 else temp.num = temp1 / temp2;//做除法 s.push(temp);//再將這個運算元壓入堆疊 } } return s.top().num;//堆疊頂元素便是后綴運算式的值 } int main() { oop['+'] = oop['-'] = 1;//設定運算子的優先級 oop['*'] = oop['/'] = 2; // freopen("d://in.txt","r",stdin); while (getline(cin, str), str != "0") { for (string::iterator it = str.begin(); it != str.end(); it++) { if (*it == ' ') str.erase(it);//把運算式中的空格全部去掉， } while (!s.empty()) s.pop();//將堆疊初始化 change();//將中綴運算式轉化為后綴運算式 printf("%.2f\n", cal());//計算并 輸出后綴運算式的值 } return 0; }
//若中綴運算式中存在著括號：
void change() { //將中綴運算式轉換為后綴運算式 node temp; for (int i = 0; i < str.length();) { if (str[i] == '(') { temp.op = '('; s.push(temp);
i++; } else if (str[i] == ')') { while (s.top().op != '(') { q.push(s.top());
s.pop(); } s.pop();
i++; } else if (str[i] >= '0' && str[i] <= '9') { temp.flag = true; temp.num = str[i++] - '0';//記錄這個運算元的第一個數位 while (i < str.length() && str[i] >= '0' && str[i] <= '9') { temp.num = temp.num * 10 + (str[i] - '0');//更新這個運算元 i++; } q.push(temp); } else { temp.flag = false; //只要運算子堆疊的堆疊頂元素比該運算子優先級高， //就把運算子堆疊頂元素彈出到后綴運算式的佇列中， while (!s.empty() && oop[str[i]] <= oop[s.top().op]) { q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp);//將運算子壓入堆疊， i++; } } while (!s.empty()) {//如果運算子堆疊中還有元素就把他彈出到后綴運算式佇列中， q.push(s.top()); s.pop(); } }
前綴運算式是從右至左掃描中綴運算式的，如果中綴運算式要轉換為前綴運算式不太方便，
若將中綴運算式轉換為前綴運算式：
步驟一：
- 初始化兩個堆疊:運算子堆疊s1，儲存中間結果的堆疊s2（上面轉換為后綴運算式時采用的是佇列的方式儲存后綴運算式，如果也采用堆疊的形式的話，輸出結果的逆序才是后綴運算式）
- 從右至左掃描中綴運算式
- 遇到運算元時，將其壓入s2
- 遇到運算子時，比較其與s1堆疊頂運算子的優先級
- 如果s1為空，或堆疊頂運算子為右括號“)”，則直接將此運算子入堆疊
- 否則，若優先級比堆疊頂運算子的較高或相等，也將運算子壓入s1
- 否則，將s1堆疊頂的運算子彈出并壓入到s2中，再次轉到(4-1)與s1中新的堆疊頂運算子相比較
- 遇到括號時
- 如果是右括號“)”，則直接壓入s1
- 如果是左括號“(”，則依次彈出S1堆疊頂的運算子，并壓入S2，直到遇到右括號為止，此時將這一對括號丟棄
- 重復步驟2至5，直到運算式的最左邊
- 將s1中剩余的運算子依次彈出并壓入s2，
- 依次彈出s2中的元素并輸出，結果即為中綴運算式對應的前綴運算式，
前綴運算式的計算機求值：
從右至左掃描運算式，遇到數字時，將數字壓入堆疊，遇到運算子時，彈出堆疊頂的兩個數，用運算子對它們做相應的計算（堆疊頂元素 和 次頂元素，堆疊頂元素在運算子前這一點與后綴運算子不同），并將結果入堆疊；重復上述程序直到運算式最左端，最后運算得出的值即為運算式的結果，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280177.html
標籤：其他
上一篇：堆疊與佇列的應用
下一篇：0605-優化器