C++代码实现逆波兰表达式

2023-07-12 23:30:04 199

本文实例为大家分享了C++实现逆波兰表达式的具体代码，供大家参考，具体内容如下

当我们输入一个数学表达式，是中缀表达式，我们首先转换为后缀表达式（逆波兰表达式），然后再进行求值。

在《大话数据结构》的104-100页有详细的介绍，下面是我理解之后的代码实现。

代码思路：

（1）首先对输入的中缀表达式合法性进行判断，boolisStringLegal(constchar*str);函数实现。

（2）然后把中缀表达式转换为后缀表达式。

（3）根据后缀表达式求出结果，doublegetTheResult(vector&vec);函数实现。

注意：表达式的运算符可以输入加、减、乘、除、括号，输入的数据为整形数据，计算结果为double型数据。

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

usingnamespacestd;

#defineMAX_STRING_LENGTH100

/*解析当前的整形数据，并把整形数据转换为string型*/
stringanalyData(constchar*str,int&i);

/*根据逆波兰表达式求表达式的值*/
doublegetTheResult(vector&vec);

/*判断该字符是否是+-*/()*/
boolisCalChar(constcharch);

/*判断输入的中缀表达式是否合法*/
boolisStringLegal(constchar*str);



/*解析当前的整形数据，并把整形数据转换为string型*/
stringanalyData(constchar*str,int&i)
{
inttemp=i++;
while(str[i]>='0'&&str[i]<='9'&&str[i]!='\0')
{
i++;
}

strings(str+temp,str+i);

returns;
}

/*根据逆波兰表达式求表达式的值*/
doublegetTheResult(vector&vec)
{
vector::iteratorit;
stacksta;

stringstrTemp;
doubled=0,d1=0,d2=0;

for(it=vec.begin();it!=vec.end();it++)
{
strTemp=(*it);

if(strTemp=="+")
{
d1=sta.top();
sta.pop();

d2=sta.top();
sta.pop();

d=d1+d2;
sta.push(d);
}
elseif(strTemp=="-")
{
d1=sta.top();
sta.pop();

d2=sta.top();
sta.pop();

d=d2-d1;
sta.push(d);
}
elseif(strTemp=="*")
{
d1=sta.top();
sta.pop();

d2=sta.top();
sta.pop();

d=d2*d1;
sta.push(d);
}
elseif(strTemp=="/")
{
d1=sta.top();
sta.pop();

d2=sta.top();
sta.pop();

d=d2/d1;
sta.push(d);
}
else
{
constchar*p=strTemp.c_str();
d=atoi(p);
sta.push(d);
}
}
returnsta.top();
}

/*判断该字符是否是+-*/()*/
boolisCalChar(constcharch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')')
{
returntrue;
}

returnfalse;
}
/*判断输入的中缀表达式是否合法*/
boolisStringLegal(constchar*str)
{
/*判断是否是空串*/
if(NULL==str)
{
returnfalse;
}

intlen=strlen(str);
inti=0;
intflag=0;

/*字符串的开头和末尾是否是数字*/
if(str[0]>'9'||str[0]<'0'||str[len-1]>'9'||str[len-1]<'0')
{
returnfalse;
}


for(i=0;str[i]!='\0';i++)
{
/*是否有除了加减乘除括号之外的字符*/
if(isCalChar(str[i])==false)
{
returnfalse;
}

/*判断是否有两个连续的符号*/
if(ioper_char;

/*存放后缀表达式*/
vectorpost_str;

/*输入中缀的表达式*/
gets(str);

/*判断输入的中缀表达式是否合法*/
if(isStringLegal(str)!=true)
{
cout<<"Thisexpressionisnotlegal."<='0'&&str[i]<='9')
{
data=analyData(str,i);
post_str.push_back(data);
i--;
}
elseif(str[i]=='(')
{
oper_char.push(str[i]);
}
elseif(str[i]==')')
{
charchtemp[2]={0};

chtemp[0]=oper_char.top();

while(chtemp[0]!='(')
{
stringstrtemp(chtemp);
post_str.push_back(strtemp);
oper_char.pop();

chtemp[0]=oper_char.top();
}
oper_char.pop();
}
elseif(str[i]=='+'||str[i]=='-')
{
charchtemp[2]={0};

/*全部出栈，但是碰到'('就要停止出栈*/
while(oper_char.size()!=0)
{
chtemp[0]=oper_char.top();
if(chtemp[0]=='(')
{
break;
}

oper_char.pop();

stringstrtemp(chtemp);
post_str.push_back(strtemp);
}

/*将当前的表达式符号入栈*/
oper_char.push(str[i]);
}
elseif(str[i]=='*'||str[i]=='/')
{
charchtemp[2]={0};
while(oper_char.size()!=0)
{
chtemp[0]=oper_char.top();
if(chtemp[0]=='('||chtemp[0]=='+'||chtemp[0]=='-')
{
break;
}
else
{
oper_char.pop();

stringstrtemp(chtemp);
post_str.push_back(strtemp);
}
}

/*将当前的表达式符号入栈*/
oper_char.push(str[i]);
}
}

/*存放表达式的栈可能还有数据*/
while(!oper_char.empty())
{
charchtemp[2]={0};
chtemp[0]=oper_char.top();
oper_char.pop();

stringstrtemp(chtemp);
post_str.push_back(strtemp);
}

/*把逆波兰表达式求值*/
cout<
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++代码实现逆波兰表达式

热门推荐

随机推荐