此页面通过工具从 csdn 导出，格式可能有问题。
题目
输入一个表达式，计算出它的值。运算符有 + - × / （ ）。
思路
这是我们学栈时碰到的一个问题，大体方法是利用双栈把中缀表达式转换成后缀表达式进行计算
------------------------------------------------------------------------------------------------
1.拆分数字与运算符
：遇到运算符截断、存储、清空。2.转后缀表达式
：栈A存放后缀表达式，栈B存放运算符
记 B栈顶运算符为a1,当前运算符为a2（若a2为数字直接 a2->A ）
1）若 a1>a2，a1->A，a2->B
1）若 a1<a2，a2->B；
2）若 a1>=a2
1.若a1>a2，a1->A；（只要该条件满足则一直执行，使得优先级高的运算符放在A中）2.将高级运算符都赶走后，要判断a1=a2 ?（ 即是否为()相遇）如果为左右括号的话就把做括号弹出，否则把a2->B。（注意与1的区别，一个）可以一直赶走比它高级的运算法，但是只能抵消一个左括号）
PS: a1>a2 表示 在此式中先算a1再算a2，a1与a2的关系在初始化中建立。
3.计算后缀表达式
: 从左往右扫描，遇到运算符则处理前两位数字
-------------------------------------------------------------------------------------------------
代码
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;
string ss;
vector<double> ans;
vector<string> s,A;
stack<char> B;
int cmp[8][8]={ {1,1,-1,-1,-1,1},
{1,1,-1,-1,-1,1},
{1,1,1,1,-1,1},
{1,1,1,1,-1,1},
{-1,-1,-1,-1,-1,0},
{1,1,1,1,0,0}};
int gec[333];
bool isNum(char a){
switch(a){
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
return false;
}
return true;
}
void init(){
gec['+']=0;
gec['-']=1;
gec['*']=2;
gec['/']=3;
gec['(']=4;
gec[')']=5;
}
void Quit(int v){
cout << "ERROR : ";
switch(v){
case 1:
cout << "DIVISION BY 0";
break;
case 2:
cout << "PARENTHESES ARE NOT EVEN";
break;
}
cout << endl;
exit(0);
}
double gen(string s){
double tmp;
sscanf(s.c_str(),"%lf",&tmp);
return tmp;
}
void check(){
stack<char> q;
for (string::size_type i(0);i!=ss.size();i++){
if (ss[i]=='(') q.push(ss[i]);
if (ss[i]==')') {
if (q.empty()) Quit(2);
if (q.top()=='(') q.push(ss[i]);
else q.pop();
}
}
if (q.size()) Quit(2);
}
void ready(){
cin >> ss;
check();
ss+=')';
string str="";
for (string::size_type i(0);i!=ss.size();i++){
if (isNum(ss[i])){
str+=ss[i];
}else {
if (str.size()) s.push_back(str);
str=ss[i];
s.push_back(str);
str="";
}
}
}
void changetype(){
B.push('(');
for (unsigned int i(0);i!=s.size();i++){
if (isNum(s[i][0])){
A.push_back(s[i]);
}else{
char ch=s[i][0];
if (cmp[gec[B.top()]][gec[ch]]<0){
B.push(ch);
}else
if (cmp[gec[B.top()]][gec[ch]]>=0){
string str;
while (cmp[gec[B.top()]][gec[ch]]>0){
str=B.top();
A.push_back(str);
B.pop();
}
if (cmp[gec[B.top()]][gec[ch]]==0){
B.pop();
}else{
B.push(ch);
}
}
}
}
}
void calcit(){
for (int i(0);i!=A.size();i++){
if (isNum(A[i][0])) {
ans.push_back(gen(A[i]));
}else{
double a1=ans[ans.size()-2];
double a2=ans[ans.size()-1];
printf("%.2f%c%.2f=",a1,A[i][0],a2);
switch (A[i][0]){
case ‘+':
a1+=a2;
break;
case ‘-':
a1-=a2;
break;
case ‘':
a1=a2;
break;
case ‘/':
if (!a2){
Quit(1);
}
a1/=a2;
break;
}
printf("%.2f\n",a1);
ans.pop_back();
ans[ans.size()-1]=a1;
}
}
printf("%.3f\n",ans[0]);
}
int main(){
init();
ready();
changetype();
calcit();
return 0;
}
