如何用C++编写个程序中缀表达式变成后缀表达式，并用后缀表达式求值

#include
#include
#include
#include

namespace{

class Expression
{
public:
Expression();
static void Remove_space(std::string &Translated);
static int Compare(char op);
static void RPN(std::string expression);
static int Clculate();
static void Display(const std::vector &opnd, const std::string &soper);

static std::vector sResult;
static std::stack snum;
};
std::vector Expression::sResult;
std::stack Expression::snum;

Expression::Expression()
{
sResult.reserve(100);
}

void Expression::Remove_space(std::string &Translate)
{
std::string::size_type position_start = 0;
std::string::size_type position_end = 0;

std::string Result;
Result.reserve(100);
while( (position_end = Translate.find_first_of(' ',position_start)) != std::string::npos)
{
std::string temp = Translate.substr(position_start,position_end - position_start);
Result += temp;
position_start = ++position_end;
}
Result += Translate.substr(position_start,position_end - position_start);
Translate = Result;
}

int Expression::Compare(char op)
{
int Level = 0;
switch(op)
{
case '+':case '-':
Level = 1;
break;
case '*':case '/':
Level = 2;
break;
default:
break;
}
return Level;
}

void Expression::RPN(std::string expression)
{
std::string::size_type nCount = expression.length();
std::string::size_type index = 0;
std::stack stmp;
bool flag = false;

stmp.push('@');
while( index < nCount)
{
if( expression[index] == '(')
{
stmp.push('(');
index++;
}
else if( expression[index] == ')')
{
while( stmp.top() != '(')
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}
stmp.pop();
index++;
}
else if( expression[index] == '+' || expression[index] == '-' ||
expression[index] == '*' || expression[index] == '/' )
{
if( expression[index] == '-' || expression[index] == '+' )
{
if(index == 0)//如果第一个数字是负数
{
index ++;
flag = true;
}
else if( expression[index-1] == '(' )//如果括号里第一个数是负数
{
index++;
flag = true;
}
else
{
while( Compare( expression[index] ) <= Compare( stmp.top() ))
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}

stmp.push( expression[index] );
index++;
}

}
else
{
while( Compare( expression[index] ) <= Compare( stmp.top() ))
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}
stmp.push( expression[index] );
index++;
}
}
else
{
std::string temp;
if(flag == true)
{
temp += expression[index - 1];
flag = false;
}
while( expression[index] >= '0' && expression[index] <= '9')
{
temp += expression[index];
index ++;
}
sResult.push_back( temp );
}
}//while

while(stmp.top() != '@')
{
if(stmp.top() == '(')
{
std::cout << "Error in expression" << std::endl;
exit(-1);
}
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}

}//RPN

int Expression::Clculate()
{
std::vector opnd;

size_t index = 0;

int num1 = 0, num2 = 0;

std::cout<< "OPND栈" << "\t\t" <<"OPTR栈" << "\t\t" <<"输入字符"<<"\t"<<"主要操作"<
for(index = 0; index < sResult.size(); ++index)
{
std::string oper = sResult[index];
if( (oper.size()>1) && (oper[0] == '+' || oper[0] == '-') )
{
snum.push( atoi(sResult[index].c_str()) );
opnd.push_back(atoi(sResult[index].c_str()));
}
else
{
switch(oper[0])
{
case '+':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 + num1);
opnd.push_back(num2 + num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "+" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '-':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 - num1);
opnd.push_back(num2 - num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "-" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '*':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 * num1);
opnd.push_back(num2 * num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "*" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '/':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
if(num1 == 0)
{
std::cerr << "Expression worng!" << std::endl;
exit(-1);
}
snum.push( num2 / num1);
opnd.push_back(num2 / num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "*" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
default:
{
snum.push( atoi(sResult[index].c_str()) );
opnd.push_back( atoi(sResult[index].c_str()) );
}
break;
}//swith
}
}//while

int result = snum.top();
snum.pop();
return result;
}

void Expression::Display(const std::vector &opnd, const std::string &soper)
{
size_t index = 0;
for(index; index< opnd.size(); index++)
{
std::cout << opnd[index] << " ";
}
std::cout<< "\t\t" << soper << "\t\t";
}

}//class

int main()
{

std::string Input;

std::cout << "please input the expression (Enter key for end)" << std::endl;
std::getline(std::cin, Input, '\n');

Expression expression;
Expression::Remove_space(Input);
Expression::RPN(Input);

std::cout << std::endl;
std::cout << "后缀表达式:" << std::endl;

for(size_t index = 0; index < Expression::sResult.size(); ++index)
{
std::cout << Expression::sResult[index] << " ";
}

std::cout << std::endl;

std::cout<< Expression::Clculate() << std::endl;
return 0;
}

please input the expression (Enter key for end)
11-(22-11)*2-(-10)+10/5

后缀表达式:
11 22 11 - 2 * - -10 - 10 5 / +
OPND栈 OPTR栈 输入字符 主要操作
11 22 11 - 11 11 出OPND栈
11 22 - 22 22 出OPND栈
11 11 + 计算22-11并将结果压OPND栈
11 11 2 * 2 2 出OPND栈
11 11 * 11 11 出OPND栈
11 22 + 计算11*2并将结果压OPND栈
11 22 - 22 22 出OPND栈
11 - 11 11 出OPND栈
-11 + 计算11-22并将结果压OPND栈
-11 -10 - -10 -10 出OPND栈
-11 - -11 -11 出OPND栈
-1 + 计算-11--10并将结果压OPND栈
-1 10 5 / 5 5 出OPND栈
-1 10 / 10 10 出OPND栈
-1 2 + 计算10*5并将结果压OPND栈
-1 2 + 2 2 出OPND栈
-1 + -1 -1 出OPND栈
1 + 计算-1+2并将结果压OPND栈
1
Press any key to continu

#include
#include
#include
#include
#include
#include

using namespace std;

int main(void)
{
cout<<"正规表达式解析器，语言：C++，作者：曹扬^_^。"< cout<<"支持符号：+（加号），-（减号），*（乘号），/（除号），(（前括号），)（后括号），^（次方）。"< cout<<"键入exit可退出。"< cout<<"括号必须配对，负数应表示为\"(0-?)\"，正数前不能加\"+\"号。"< cout<<"违反上述规则造成结果错误或当机后果自负！！"< cout<<"注：计算浮点数时结果为近似值。"< cout<<"-------------------------------------------------------------------------"< cout< while(true)
{
stack cstack;
//cstack储存读入的符号
stack dstack;
//dstack储存读入的数字
char str[1000],s,covstr[1200];
//str储存原始算式，s标记扫描到的是数字还是符号，covstr储存转换成的逆波兰式
start:
cstack.c.clear();
dstack.c.clear();
cin>>str;
{
int k=0;
for(unsigned int i=0;i {
if(str[i]=='(')
k++;
else if(str[i]==')')
k--;
}
if(k!=0)
{
cout<<"括号没有配对！"< goto start;
}
}
if(strcmp(str,"exit")==0)
break;
//如果输入的是exit就退出
unsigned int temp=strlen(str),k=0;
//把原始算式的长度存在temp里，标记k指向第一个字符
if(isdigit(str[0]))
s='n';
else
s='s';
//判断第一个字符是数字还是符号
for(unsigned int i=0;i {
//判断读入的是什么符号
if(isdigit(str[i])) //如果是数字就看看上次读入的是
{ //什么，如果也是数字，就把它们
if(s=='n') //拼在一起，如果不是，就在中间
covstr[k++]=str[i]; //插入一个空格
else
{
covstr[k++]=' ';
covstr[k++]=str[i];
}
s='n';
}
else if(str[i]=='.') //如果是小数点，就直接拼在一起
{
covstr[k++]=str[i];
}
else //如果是符号，就开始判断是什么
{ //符号，优先级高的排在前
s='s';
if(str[i]=='^')
{
if(!cstack.empty())
while(cstack.top()=='^')
{
covstr[k++]=' ';
covstr[k++]=cstack.top();
cstack.pop();
if(cstack.empty())
break;
}
cstack.push(str[i]);
}
else if(str[i]=='*'||str[i]=='/')
{
if(!cstack.empty())
while(cstack.top()=='*'||cstack.top()=='/'||cstack.top()=='^')
{
covstr[k++]=' ';
covstr[k++]=cstack.top();
cstack.pop();
if(cstack.empty())
break;
}
cstack.push(str[i]);
}
else if(str[i]=='+'||str[i]=='-')
{
if(!cstack.empty())
while(cstack.top()=='+'||cstack.top()=='-'||cstack.top()=='*'||cstack.top()=='/'||cstack.top()=='^')
{
covstr[k++]=' ';
covstr[k++]=cstack.top();
cstack.pop();
if(cstack.empty())
break;
}
cstack.push(str[i]);
}
else if(str[i]=='(')
{
cstack.push(str[i]);
}
else if(str[i]==')')
{
while(!(cstack.top()=='('))
{
covstr[k++]=' ';
covstr[k++]=cstack.top();
cstack.pop();
}
cstack.pop();
}
}
}
while(!cstack.empty())
{
covstr[k++]=' ';
covstr[k++]=cstack.top();
cstack.pop();
}
covstr[k++]=' ';covstr[k]='\0';
cout<<"逆波兰式："< //计算逆波兰式
char *p,*q;
p=covstr;
q=strchr(p,' ');
*q='\0';
double temp1,temp2;
while(true)
{
if(strcmp(p,"+")==0)
{
temp2=dstack.top();
dstack.pop();
temp1=dstack.top();
dstack.pop();
dstack.push(temp1+temp2);
}
else if(strcmp(p,"-")==0)
{
temp2=dstack.top();
dstack.pop();
temp1=dstack.top();
dstack.pop();
dstack.push(temp1-temp2);
}
else if(strcmp(p,"*")==0)
{
temp2=dstack.top();
dstack.pop();
temp1=dstack.top();
dstack.pop();
dstack.push(temp1*temp2);
}
else if(strcmp(p,"/")==0)
{
temp2=dstack.top();
dstack.pop();
temp1=dstack.top();
dstack.pop();
if(temp2==0)
{
cout<<"除数不能为0！"< goto start;
}
dstack.push(temp1/temp2);
}
else if(strcmp(p,"^")==0)
{
temp2=dstack.top();
dstack.pop();
temp1=dstack.top();
dstack.pop();
if(temp1==0&&temp2==0)
{
cout<<"0的0次方无意义！"< goto start;
}
dstack.push(pow(temp1,temp2));
}
else
{
dstack.push(atof(p));
}
p=q;
p++;
q=strchr(p,' ');
if(q==NULL)
break;
*q='\0';
}
cout<<"结果："< }
return 0;
}