HDU1237--简单计算机--中缀转后缀

本文主要是介绍HDU1237--简单计算机--中缀转后缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简单计算器

  
1 + 2
4 + 2 * 5 - 7 / 11
0

  
3.00
13.36

数据结构刚刚讲到中缀转后缀，发现后缀表达式挺有用的。。。

顺手写了一个中缀转后缀+计算后缀表达式值的模板：

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--简单计算机--中缀转后缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！