簡單計(jì)算器
[codeup 1918]
題目描述
讀入一個只包含 +, -, *, / 的非負(fù)整數(shù)計(jì)算表達(dá)式，計(jì)算該表達(dá)式的值。
輸入
測試輸入包含若干測試用例，每個測試用例占一行，每行不超過200個字符，整數(shù)和運(yùn)算符之間用一個空格分隔。沒有非法表達(dá)式。當(dāng)一行中只有0時輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。
輸出
對每個測試用例輸出1行，即該表達(dá)式的值，精確到小數(shù)點(diǎn)后2位。
樣例輸入
30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
0
樣例輸出
12178.21
//測試數(shù)據(jù)
//輸入：
1+ 3 * 5 / 4 * 8 / 9 * 6 * 2 / 3/7 + 3 * 8 / 2
12 + 78 / 4 * 6 * 7/3 - 12 - 13 - 24 * 25 / 6
12 + 781 / 19 * 6 * 7 / 13 - 24 * 25 / 63
985211 * 985/211
2 / 3 * 4
2 * 3 / 49
5 + 2 * 3 / 49 - 4 / 13
0
//輸出：
14.90
160.00
135.28
4599207.75
2.67
0.12
4.81
思路
- 先將中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式
1.1 需要有一個存放操作符的棧和一個存放后綴表達(dá)式的隊(duì)列
1.2 操作數(shù)可能不止一位，需要對一位一位進(jìn)行判斷是否需要合并再加入后綴表達(dá)式
1.3 操作符需要搞清楚加減乘除的優(yōu)先級，可以用map來映射其中關(guān)系；同時，操作符的優(yōu)先級相比，何時彈出，何時壓棧，非常關(guān)鍵（以2 / 3 * 4為例）
1.4 如中綴表達(dá)式掃描完后，需要將剩余的操作符棧中元素依次彈出入隊(duì)列 - 計(jì)算后綴表達(dá)式
2.1. 操作數(shù)壓入棧
2.2 操作符則彈出兩個操作數(shù)（后彈出為第一操作數(shù)，先彈出為第二操作數(shù)）
2.3 最后棧中存在的數(shù)即為答案
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <map>
using namespace std;
struct node {
double num; //操作數(shù)
char op; //操作符
bool flag; //操作符為false,操作數(shù)為true
};
string str;
stack<node> s; //在change()存放操作符,在Cal()中存放操作數(shù)
queue<node> q; //存放后綴表達(dá)式的隊(duì)列
map<char,int> op; //關(guān)于操作符的映射
void Change() { //中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
double num; //沒有用 晴神筆記為什么設(shè)置這個？？
node temp;
for(int i=0; i<str.length(); ) {
if(str[i]>='0' && str[i]<= '9') { //若是操作數(shù)
temp.flag = true;
temp.num = str[i++] - '0'; //操作數(shù)可能不是個位數(shù),因此要存儲多位
while( i<str.length() && str[i] >='0' && str[i]<='9') {
temp.num = temp.num *10 + (str[i] - '0'); //若為十位以上,則將化為十進(jìn)制
i++; //存入后綴表達(dá)式的隊(duì)列中
}
q.push(temp); //存入后綴表達(dá)式的隊(duì)列中
} else { //若是操作符
temp.flag = false;
while(!s.empty() && op[str[i]] <= op[s.top().op] ) { //比較當(dāng)前操作符與棧頂?shù)膬?yōu)先級,不大于的都彈出
q.push(s.top()); //注:s.top()為node型, node.op == '+'
s.pop();
}
temp.op = str[i] ; //將當(dāng)前操作符
s.push(temp); // 入棧
i++;
}
}//for
while(!s.empty() ) { //若遍歷完棧中還有操作符,全部彈出
q.push(s.top());
s.pop();
}
}
double Cal() { //計(jì)算后綴表達(dá)式
double x1,x2;
node temp,cur;
while(!q.empty()) {
cur = q.front(); //cur 記錄隊(duì)首
q.pop(); //出隊(duì)列
if( cur.flag == true) s.push(cur); //若為操作數(shù),則入棧
else { //若為操作符,則彈出2個操作數(shù)
x2 = s.top().num; //先彈第2個數(shù)
s.pop();
x1 = s.top().num; //再彈第1個數(shù),順序不能亂
s.pop();
temp.flag = true; //臨時記錄一個操作數(shù)
if(cur.op == '+') temp.num = x1 + x2;
else if(cur.op == '-') temp.num = x1 - x2;
else if(cur.op == '*' ) temp.num = x1 * x2;
else if(cur.op == '/') temp.num = x1 / x2;
s.push(temp);
}
}
return s.top().num; //最后剩下的就是結(jié)果
}
int main() {
op['+'] = op['-'] = 1;
op['*'] = op['/'] = 2;
while(getline(cin,str) , str !="0") { //getline是獲取一整行的字符串
string::iterator it ;
for(it = str.end(); it != str.begin() ; it--) {
if(*it == ' ') //注意這是指針與int型的比較,不是" "
str.erase(it); //將字符串的空格全部清除
}
while(!s.empty()) s.pop(); //初始化棧,避免棧不為空,留了東西
Change();
printf("%.2lf\n" , Cal());
}
return 0;
}
感悟
- 需要提前考慮到因?yàn)槌ǘa(chǎn)生的浮點(diǎn)數(shù)，在需要的地方設(shè)置double
- 這一句話沒有用i++形式出現(xiàn)，而是在需要的時候?qū)進(jìn)行操作，妙！
for(int i=0; i<str.length(); )
- 需要巧妙使用map映射，在此乘除和加減的優(yōu)先級不同就可用map來實(shí)現(xiàn)
- 在其中大量涉及到棧和隊(duì)列的應(yīng)用，必要時需要在草稿紙手動實(shí)現(xiàn)壓棧出棧、出隊(duì)入隊(duì)的操作
- 不要遺漏細(xì)節(jié)，題目中還需要對輸入時空格進(jìn)行處理
- 拓展：添加對不合法對象的處理；如果有括號時的處理（檢查左括號 '(' 和右括號 ')' )
