C++|codeup1918 计算中缀表达式（C++） C++|算法代码

题目题目描述读入一个只包含+、-、*、/的非负整数计算表达式，计算该表达式的值。
输入格式测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中石油0时输入结束，相应的结果不要输出。
输出格式对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
样例输入 30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
样例输出 12178.21
分析

主要过程是通过给出的中缀表达式转换成后缀表达式，然后计算出结果；
注意如何把包括空格在内的一行字符串读入，以及如何解决读取的操作数可能不止一位的情况；
算法需要频繁使用栈和队列，使用STL中的stack和queue类比较方便。

下列给出算法的主要思路流程：
步骤1：中缀表达式转后缀表达式
while(中缀队列非空)
{
if(当前指向的是操作数)
加入到后缀队列中；
else if(当前指向的是操作符)
{
if(栈为空||当前指向的操作符优先级高于栈顶操作符优先级)
压入操作符栈；
else
{
while(栈为空&&当前指向操作符优先级低于或等于栈顶操作符优先级)
弹出并加入后缀队列；
压入操作符栈；
}
}
操作栈内操作符依次弹出并放入后缀队列.
【C++|codeup1918 计算中缀表达式（C++）】步骤2：计算后缀表达式
while(后缀队列非空)
{
if(当前指向队列元素是操作数)
压入栈内；
else //是操作符
{
先后从栈中弹出第二操作数、第一操作数(注意顺序)；
结合操作符计算并将结果压入栈内；
}
}
代码

#include #include #include #include #include #include #include #include using namespace std; map mp; struct node { float num; char c; bool flag; //flag=true:是操作数 flag=false:是操作符 }; int isOperator(char c)//判断是否是操作符，如果是则返回优先级(2:乘除 1:加减)，否则返回-1(表示是操作数) { return mp[c]; }//将字符串（中缀表达式）转成后缀表达式 void GetPostfix(queue infixQ,queue &postfixQ) { int i=0,level; stack S; while(!infixQ.empty())//遍历中缀表达式中所有字符 { node nd=infixQ.front(); if(nd.flag==true)//是操作数 { nd.flag=true; postfixQ.push(nd); //加入后缀队列中 } else//是操作符 { nd.flag=false; if(S.empty()||isOperator(nd.c)>isOperator(S.top().c))//当前OP优先级高于栈顶OP S.push(nd); else//当前OP优先级小于等于栈顶OP { while(!S.empty()&&isOperator(nd.c)<=isOperator(S.top().c)) { node nd0=S.top(); //将栈顶操作符弹出并装入后缀队列中 nd0.flag=false; S.pop(); postfixQ.push(nd0); } S.push(nd); } } infixQ.pop(); } while(!S.empty())//栈内剩余操作符弹出加入后缀队列 { node nd=S.top(); S.pop(); postfixQ.push(nd); } return; }//将后缀表达式计算出结果 void Calcu(queue Q) { stack S; //装当前结果的栈 while(!Q.empty()) { node nd=Q.front(); if(nd.flag==true)//是操作数 { S.push(nd.num); //cout<<"push:"< strs; //建一个string类型的容器 string line; while(getline(fileIn,line))//获得一行的字符串（包括空格） { strs.push_back(line); }for(int i=0; i.size(); i++) { if(strs[i]!="0")//没有到结尾行 { //清空字符串中的空格后放入中缀队列中 queue infixQ; //中缀队列 int pos=0; while(pos[i].size()) { if(strs[i][pos]>='0'&&strs[i][pos]<='9')//是数字 { node nd; nd.num=strs[i][pos]-'0'; nd.flag=true; pos++; while(pos[i].size()&&strs[i][pos]>='0'&&strs[i][pos]<='9')//后面的仍是数字 { float tmp; tmp=strs[i][pos]-'0'; nd.num=nd.num*10+tmp; pos++; } infixQ.push(nd); } else if(strs[i][pos]==' ') pos++; else { node nd; nd.c=strs[i][pos]; nd.flag=false; pos++; infixQ.push(nd); } } queue postfixQ; //后缀队列 GetPostfix(infixQ,postfixQ); Calcu(postfixQ); } } return 0; }