堆栈的应用——计算器

题目描述思路==中缀表达式转后缀表达式====计算后缀表达式的值== 代码实现

题目描述

读入一个只包含+，-，*，/以及括号的计算表达式，计算该表达式的值。 样例输入：30 / 90 + 12 * 6 - ( 2 - 4 ) ，下一行输入0表示输入结束，最后结果保留两位小数。

思路

中缀表达式转后缀表达式

中缀表达式描述：

分别构造一个堆栈st和一个队列q，用来保存临时的操作符和后缀表达式。从左向右扫描中缀表达式，如果碰到操作数，就将它压入q，如果碰到操作符则将它与st顶端的操作符比较优先级： 栈顶的优先级小于当前的优先级，直接将操作符压入st大于或等于下，不断将st中操作符弹出至q，直到栈顶操作符优先级小于当前优先级或者为空。如果碰到了 ( ，则将之后的操作符按照上述两条规则压入st中，直到遇到 ），将（ 之后的 操作符全部弹出到q中。 举个例子： 5 + ( 3 *4 + 6 ) --> 534\*6++ 直到遍历完表达式后，如果st中未空，将st中元素全部弹出至q中，至此，后缀表达式完成。

计算后缀表达式的值

由于先前的st已空，现在拿它当临时的操作数栈。首先从q的左边开始遍历，如果遇到操作数就压入st，如果遇到操作符，则取出st顶端的两个操作数， 切记第一个取出的是操作数2，第二个取出的是操作数1，做运算后再压回st中，以此类推，直到计算完毕。

---

代码实现

#include<stdio.h> #include<iostream> #include<map> #include<string> #include<stack> #include<queue> using namespace std; struct node{ double num; //操作数 char op; // 操作符 bool flag; //true为数， false为符号 }; string str; stack<node> s; queue<node> q; map<char, int> op; void change(){ // 中缀表达式转后缀表达式 double num; node temp; for(int i=0; i<str.length();){ if(str[i]>='0' && str[i]<='9'){ temp.flag = true; temp.num = str[i]-'0'; i++; 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; if(str[i]=='('){ // 如果是前括号，直接压入栈中并进行下一个的判断 temp.op = str[i]; s.push(temp); i++; continue; } if(str[i]==')'){ // 如果是后括号，将前括号之后的操作符全部压入后缀表达式中,并进行下一个的判断 while(s.top().op != '('){ q.push(s.top()); s.pop(); } s.pop(); //将前括号删去 i++; continue; } while(!s.empty() && op[str[i]]<=op[s.top().op]){ q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } while(!s.empty() && i==str.length()){ // 将剩余的操作符放入后缀表达式 q.push(s.top()); s.pop(); } } } void show(){ node x; printf("表达式为:\n"); while(!q.empty()){ x = q.front(); q.pop(); if(x.flag == true) printf("%.2f", x.num); else printf("%c", x.op); } } //查看后缀表达式的代码，但是使用这个以后会清空队列导致calculate无法使用。 double calculate(){ // 计算后缀表达式 double temp1, temp2; node cur, temp; while(!q.empty()){ cur = q.front(); 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(){ op['+'] = op['-'] = 1; op['*'] = op['/'] = 2; while(getline(cin, str), str!="0"){ for(string::iterator it = str.end(); it != str.begin(); it--){ if(*it == ' '){ str.erase(it); } } while(!s.empty()) s.pop(); change(); // show(); printf("%.2f\n", calculate()); } return 0; }