数据结构 栈应用2 表达式求值
表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的一个典型例子。
表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的一个典型例子。
Question
表达式求值是进行数据处理的最基本操作。请编写程序完成一个简单算术表达式的求值。要求如下：
- 运算符包括：
+、-、*、-、^(乘方)、括号 - 运算量为数值常量，根据自己的能力可以对运算量做不同的约束，例如1位整数、多位整数、实数等（会有不同的测试用例）；
- 输入：一行，即表达式，以“=”结束。例如：
5*(8-3)+6/5=
- 输出：一行，即表达式的值。结果值为整数时输出为整数，如果有小数时保留5位小数。
26.20000
问题与分析
栈
栈是特殊的线性表，其一端固定，只允许在另一端插入或删除。其特性是“先进后出”。
表达式的书写形式
- 前缀式
+ × a b × - c / d e f - 中缀式
a × b + (c - d / e) × f - 后缀式
a b × c d e / - f × +
前缀式的运算规则
连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;
运算符出现的顺序与运算顺序相反
中缀式与后缀式略。其中中缀式是我们最常书写的形式。
后缀式的运算
- 是操作数，入栈
- 是符号，取出两个操作数运算后入栈
- 表达式处理完毕后栈内唯一元素即运算结果
中缀式转换为后缀式
直接对中缀式求值
类似中缀式转后缀式的过程，把运算量的输出改为“入OPND栈”，把运算符的“输出”改为“计算”：根据运算符，出栈需要的运算量，计算值，结果作为运算量再入栈。其他不需要变化。
遇到的其他问题
- 用float交这道题会出错，精度不够，要用double。
- 判断有没有小数的方法：截断后与原值相减绝对值在误差允许范围内。不能用相等，因为浮点数的存储性质，直接比较相等很可能出错。
- 通过
cin的setiosflags和setprecision格式化提交也会有问题，因为这样竟然是进行四舍五入的……
Answer
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <cstdio>
using namespace std;
template <class T>
class mystack{
private:
T *data;
int maxsize;
int top;
public:
mystack(){
maxsize=1;
data=new T[maxsize];
top=-1;
}
bool isEmpty(){
return top==-1;
}
T getTop(){
if(top>-1){
return data[top];
}
return NULL;
}
void pop(){
if(top>=0){
top--;
}
}
void expand(){
T*tmp=new T[maxsize*2];
for(int i=0;i<maxsize;i++){
tmp[i]=data[i];
}
maxsize*=2;
delete[] data;
data=tmp;
}
void push(T x){
if(top+1==maxsize){
expand();
}
data[++top]=x;
}
~mystack(){
delete[] data;
}
};
int getid(char x){
string str="+-*/^()#";
for(int i=0;i<str.size();i++){
if(x==str.at(i)){
return i;
}
}
return -1;
}
/**
* 栈外符号大于栈内，返回1，小于返回-1，其他返回0
* @param ch1 栈内的符号
* @param ch2 栈外的符号
*/
int cmpp(char ch1,char ch2){
string chart[]={
//+-*/^()#
">><<<<>>",//+
">><<<<>>",//-
">>>><<>>",//*
">>>><<>>",///
">>>>><>>",//^
"<<<<<<=X",//(
">>>>>X>>",//)
"<<<<<<X="//#
};
if(chart[ch1].at(ch2)=='<'){
return 1;
}else if(chart[ch1].at(ch2)=='>'){
return -1;
}
return 0;
}
template <class Type>
Type stringToNum(const string& str)
{
istringstream iss(str);
Type num;
iss >> num;
return num;
}
double cal(string str){
mystack<char>* OPTR=new mystack<char>();
mystack<double>* OPND=new mystack<double>();
OPTR->push('#');
string buf="";//数值缓冲，使数值作为整体处理
double res;//返回结果
for(int i=1;i<str.size();i++){
char x=str.at(i);
if(getid(x)==-1){
buf+=x;
}else{
if(buf.size()>0){
OPND->push(stringToNum<double>(buf));
buf="";
}
switch(cmpp(getid(OPTR->getTop()),getid(x))){
case 1:
OPTR->push(x);
continue;
case -1:
//计算
double tmp1,tmp2,tmp;
tmp2=OPND->getTop();
OPND->pop();
tmp1=OPND->getTop();
OPND->pop();
switch(OPTR->getTop()){
case '+':
tmp=tmp1+tmp2;
break;
case '-':
tmp=tmp1-tmp2;
break;
case '*':
tmp=tmp1*tmp2;
break;
case '/':
tmp=tmp1/tmp2;
//可以进行除数为0的判断
break;
case '^':
tmp=pow(tmp1,tmp2);
break;
}
OPND->push(tmp);
OPTR->pop();
i--;
continue;
case 0:
OPTR->pop();
continue;
}
}
}
res=OPND->getTop();
delete OPTR;
delete OPND;
return res;
}
int main()
{
string str;
getline(cin,str);
str="#"+str;
str.erase(str.size()-1);
str+="#";
double res=cal(str);
if(abs(double(int(res))-res)<0.000001){
cout<<res<<endl;
}else{
cout<<setiosflags(ios::fixed)<<setprecision(5)<<int(1e5*res)/1e5<<endl;
}
return 0;
}
最后修改于 2019-04-25