本文主要是介绍HDU1237--简单计算机--中缀转后缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
简单计算器
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 11015 Accepted Submission(s): 3580
Problem Description
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
Input
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
Output
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
Sample Input
1 + 2 4 + 2 * 5 - 7 / 11 0
Sample Output
3.00 13.36
Source
浙大计算机研究生复试上机考试-2006年
Recommend
JGShining
数据结构刚刚讲到中缀转后缀，发现后缀表达式挺有用的。。。
顺手写了一个中缀转后缀+计算后缀表达式值的模板：
ORZ。。。。。代码有点长，不过一炮就过了。
代码思路很清晰，见注释：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int maxnum=210;char mid[maxnum];//中缀表达式
char last[maxnum];//后缀表达式
stack <char> stackop;//存储operator的栈
stack <double> temp;//最后存储答案更新答案的栈//计算每个操作符的权值
int val(char x)
{switch(x){case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '(':return 3;case ')':return 3;//case '{':return 4;这两个没在代码中体现//case '}':return 4;default:return 0;}
}
//中缀转后缀，读入中缀串的长度，返回后缀串的长度
//中缀表达式可以有空格（如题目中所描述的）也可以没有空格
//返回的后缀表达式是每一段字符串都用空格分开的
int midToLast(int length)//length是原串长度
{int index=0;//遍历时last后缀表达式访问的元素下标for(int i=0;i<length;){if(mid[i]==' ')++i;else if(mid[i]<='9'&&mid[i]>='0'){last[index++]=mid[i++];while(mid[i]<='9'&&mid[i]>='0'){last[index++]=mid[i++];}last[index++]=' ';}else{int value=val(mid[i]);if(mid[i]==')')//如果是左括号就一直弹栈直到遇到一个右括号{while(!stackop.empty()&&stackop.top()!='('){last[index++]=stackop.top();stackop.pop(); //切记！STL中stack的pop是没有返回值的last[index++]=' ';}stackop.pop();++i;}else{while(!stackop.empty()&&val(stackop.top())>=value&&stackop.top()!='(')//如果是别的就一直弹栈，直到遇到一个优先级比自己低的。要么除非遇到一个右括号。//即，右括号只有在遇到左括号的时候才能被弹出{last[index++]=stackop.top();stackop.pop(); //切记！STL中stack的pop是没有返回值的last[index++]=' ';}stackop.push(mid[i]);++i;}}}while(!stackop.empty())//将还未弹出栈的operator全部赋给last后缀表达式{last[index++]=stackop.top();stackop.pop();last[index++]=' ';}return index;
}//计算后缀表达式的值，返回的是一个double类型的变量
double cal(int length)//length是原串长度
{for(int i=0;i<length;){if(last[i]==' ')++i;else if(last[i]>='0'&&last[i]<='9'){double number=last[i++]-'0';while(last[i]>='0'&&last[i]<='9'){number=number*10+last[i++]-'0';}temp.push(number);++i;}else{double temp1=temp.top();temp.pop();double temp2=temp.top();temp.pop();double temp3;switch(last[i]){case '+':{temp3=temp2+temp1;break;}case '-':{temp3=temp2-temp1;break;}case '*':{temp3=temp2*temp1;break;}case '/':{temp3=temp2/temp1;break;}}temp.push(temp3);++i;}}return temp.top();
}int main()
{while(gets(mid))//读入一行{if(strcmp(mid,"0")==0) break;int len_initial=strlen(mid);int len_last=midToLast(len_initial);cout<<last<<endl;printf("%.2lf\n",cal(len_last));}return 0;
}
这篇关于HDU1237--简单计算机--中缀转后缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
