#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
const int maxSize=50;
const double A=0.120;
const double B=0.130;
const double C=0.140;
const double D=0.150;
const double PoxfixExpFlag=-3.244;
/*****************************************************栈类**********************************************************************/
template<class T>
class Stack
{
private:
int maxSize;
int top;
T *st;
public:
Stack(int a);
void Clear();
bool Push(const T& item);
bool Pop(T &item);
bool Top(T &item);
bool isEmpty();
bool isFull();
};
/***********************栈类实现 *************************/
template<class T>
Stack<T>::Stack(int a)
{
maxSize=a;
st=new T[maxSize];
top=-1;
}
template<class T>
bool Stack<T>::Push(const T &item)
{
if(isFull())
return false;
st[++top]=item;
return true;
}
template<class T>
bool Stack<T>::Pop( T & item)
{
if(isEmpty())
return false;
item=st[top--];
return true;
}
template<class T>
bool Stack<T>::isEmpty()
{
if(top==-1) return true;
return false;
}
template<class T>
bool Stack<T>::Top( T & item)
{
if(isEmpty())
return false;
item=st[top];
return true;
}
template<class T>
bool Stack<T>::isFull()
{
if(top==maxSize-1)return true;
return false;
}
/***********************栈类实现 *************************/
/*****************************************************栈类**********************************************************************/
/*****************************************************负责计算类 函数核心************************************************************/
class Calculate{
public:
int In[8];
int Out[8];
char cha[8];
double PoxfixExp[maxSize];
Calculate();
bool isOp(char c);//检测是否为操作符
int checkPre(char out,char in);//检测栈外栈内运算符的优先级
double* Calcu(char *str);//负责将中缀转变为后缀
double jiSuanResult(double *);//负责计算后缀表达式的结果
/*后缀表达式为double型 负责char型运算符和double型之间的转换*/
double optoDou(char op);
char optoCha(double op);
};
/***********************Calculate类实现 *************************/
Calculate::Calculate()
{
cha[0]='('; In[0]=1; Out[0]=8;
cha[1]='^'; In[1]=7; Out[1]=6;
cha[2]='*'; In[2]=5; Out[2]=4;
cha[3]='/'; In[3]=5; Out[3]=4;
cha[4]='%'; In[4]=5; Out[4]=4;
cha[5]='+'; In[5]=3; Out[5]=2;
cha[6]='-'; In[6]=3; Out[6]=2;
cha[7]=')'; In[7]=8; Out[7]=1;
for(int i=0;i<maxSize;i++)PoxfixExp[i]=PoxfixExpFlag;
}
bool Calculate::isOp(char c)//检测是否为操作符
{ bool flag=1;
int i;
for(i=0;i<8;i++)
if(c==cha[i]) break;
if(i==8) flag=0;
return flag;
}
int Calculate::checkPre(char out,char in)//检测栈外栈内运算符的优先级
{
int o,i;
for(int j=0;j<8;j++)
{
if(cha[j]==in){ i=In[j]; }
if(cha[j]==out){ o=Out[j];}
}
if(o>i)return 1;
if(o==i)return 0;
if(o<i)return -1;
}
double* Calculate::Calcu(char *str)//负责将中缀转变为后缀
{
int s=0;
int p=0;
double te=0;
Stack<char>Temp(maxSize);
for(s=0;str[s]!='\0';s++)
{
if(!isOp(str[s]))//处理操作数
{
te=te*10+str[s]-'0'; //确保识别多位数 如10,32
if(str[s+1]=='\0')//特殊处理中缀表达式的最后一位操作数
{ if(te!=0) PoxfixExp[p++]=te;}
}
else//处理操作符
{
if(te!=0) //同样为了确保识别多位数 如10,32
{PoxfixExp[p++]=te;
te=0; }
if(Temp.isEmpty()) {Temp.Push(str[s]);}
else
{
char In,Out=str[s];
Temp.Top(In);
int result=checkPre(Out,In);
if(result==-1)
{
while(result!=1&&result!=0)
{//栈外小于栈内优先级 栈内元素持续弹出 直到内大于外压入 或左右括号相遇 或栈空
char op;
Temp.Pop(op);
PoxfixExp[p++]=optoDou(op);
if(Temp.isEmpty()) break;
Temp.Top(In);
result=checkPre(Out,In);
}
if(result==0) {char t; Temp.Pop(t);}//清除栈内的括号
else Temp.Push(str[s]);
}
else if(result==1) Temp.Push(str[s]);//栈外大于栈内优先级 栈外元素压入
else if(result==0) {char t; Temp.Pop(t);}//栈外为右括号 且栈内为左括号 清除栈内的括号
}
}
}
while(!Temp.isEmpty())//继续读取栈内元素
{
char op;
Temp.Pop(op);
PoxfixExp[p++]=optoDou(op);//将操作符标记为double型变量存入后缀表达式数组
}
return PoxfixExp;
}
double Calculate::jiSuanResult(double * PoxfixExp)//负责计算后缀表达式的结果
{
double Res;
int s;
Stack<double>Temp(maxSize);
for( s=0;PoxfixExp[s]!=PoxfixExpFlag;s++)
{
if(optoCha(PoxfixExp[s])=='!')//若为数字直接压入栈
Temp.Push(PoxfixExp[s]);
else//若为操作符从栈中取出两个数运算 并将结果压入栈中
{
double a,b;
Temp.Pop(a);
Temp.Pop(b);
if(optoCha(PoxfixExp[s])=='+') Res=a+b;
else if(optoCha(PoxfixExp[s])=='-') Res=b-a;
else if(optoCha(PoxfixExp[s])=='*') Res=a*b;
else if(optoCha(PoxfixExp[s])=='/') Res=b/a;
Temp.Push(Res);
}
}
return Res;
}
double Calculate::optoDou(char op)
{
if(op=='+') return A;
if(op=='-') return B;
if(op=='*') return C;
if(op=='/') return D;
}
char Calculate::optoCha(double op)
{
if(op==A) return '+';
else if(op==B) return'-';
else if(op==C) return '*';
else if(op==D) return'/' ;
else return '!';
}
/*****************************************************负责计算类 函数核心************************************************************/
/********************************此函数检测括号匹配******************************************************/
bool CheckPaMatch(char* str)
{
Stack<char> temp(maxSize);
int i=0;
bool truth=1;
char flag;//检测括号匹配
for( ;str[i]!='\0';i++)
{
if(str[i]=='[') temp.Push(str[i]);
else if(str[i]=='(') temp.Push(str[i]);
else if(str[i]=='{') temp.Push(str[i]);
//括号匹配
else if(str[i]==')'||str[i]=='}'||str[i]==']')
{
if(temp.isEmpty())
{ truth=0;
break;
}
temp.Pop(flag);
if(flag=='('&&str[i]!=')'||flag=='{'&&str[i]!='}'||flag=='['&&str[i]!=']')
{ truth=0;
break;
}
}
}
if(!temp.isEmpty()) truth=0;
return truth;
}
/**********************************主函数***********************************************/
int main()
{
char str[maxSize]; int s=0;
double *PoxfixExp; int p=0;
double Result;
Calculate pre;
Stack<char>Temp(maxSize);
//输入中缀表达式
cin>>str;
//检测括号匹配
if(!CheckPaMatch(str)) {cout<<"表达式括号不匹配";return 1;}
//转后缀
PoxfixExp=pre.Calcu(str);
//输出后缀表达式
for(int i=0;PoxfixExp[i]!=PoxfixExpFlag;i++)
{
if(pre.optoCha(PoxfixExp[i])=='!')
cout<<PoxfixExp[i];
else
cout<<pre.optoCha(PoxfixExp[i]);
}
//计算后缀表达式的结果并输出
Result=pre.jiSuanResult(PoxfixExp);
cout<<"="<<Result<<endl;
return 0;
}
运行环境：codeblocks vc++
我自己写的 可以参考一下