C++实现中缀表达式转前、后缀

#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isInt(char ch)
{
if(ch>='0'&&ch<='9')
return true;
return false;
}
bool isOperator(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
return true;
return false;
}
int opLevel(char ch)
{
int level;
switch(ch)
{
case'+':
case'-':
level=1;
break;
case'*':
case'/':level=2;
break;
default:
level=0;
break;
}
return level;
}
/*中缀-->前缀 算法
1)求输入串的逆序。
2)检查输入的下一元素。
3)假如是操作数,把它添加到输出串中。
4)假如是闭括号,将它压栈。
5)假如是运算符,则
i)假如栈空,此运算符入栈。
ii)假如栈顶是闭括号,此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符,此运算符入栈。
iv)否则,栈顶运算符出栈并添加到输出串中,重复步骤5。
6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
7)假如输入还未完毕,跳转到步骤2。
8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
9)求输出串的逆序。
*/
string priOrder(string myStr)
{
stack<char> opStack;
string result;
for(int i=myStr.length()-1; i>=0; i--)
{
char ch=myStr[i];
if(isInt(ch))
{
result.push_back(ch);
}
else if(')'==ch)
{
opStack.push(ch);
}
else if(isOperator(ch))//操作符
{
while(true)
{
if(opStack.empty()||opStack.top()==')'||(opLevel(ch)>=opLevel(opStack.top())))
{
opStack.push(ch);
break;
}
else
{
result.push_back(opStack.top());
opStack.pop();
}
}
}
else if('('==ch)
{
while(opStack.top()!=')')
{
result.push_back(opStack.top());
opStack.pop();
}
opStack.pop();
} }
while(!opStack.empty())
{ result.push_back(opStack.top());
opStack.pop(); }
return result; }
/*中缀-->后缀 算法
*/
string postOrder(string myStr)
{
string result;
stack<char> opStack;
for(int i=0; i<myStr.length(); i++)
{
char ch=myStr[i];
if(isInt(ch))
{
result.push_back(ch);
}
else if('('==ch)
{
opStack.push(ch);
}
else if(isOperator(ch))
{
while(true)
{
if(opStack.empty()||opStack.top()=='('||opLevel(ch)>=opLevel(opStack.top()))
{
opStack.push(ch);
break;
}
else
{
result.push_back(opStack.top());
opStack.pop();
}
}
}
else if(')'==ch)
{
while(opStack.top()!='(')
{
result.push_back(opStack.top());
opStack.pop();
}
opStack.pop();
} }
while(!opStack.empty())
{
result.push_back(opStack.top());
opStack.pop();
}
return result;
}
int main()
{
string myStr;
cin>>myStr;
string result;
result=priOrder(myStr);
for(int i=result.length()-1; i>=0; i--)
{
cout<<result[i];
}
cout<<endl;
result=postOrder(myStr);
for(int i=0; i<=result.length(); i++)
{
cout<<result[i];
}
return 0;
}

  

上一篇:ES 16 - 对Elasticsearch中的索引数据进行增删改查 (CRUD)


下一篇:Summary of java stream classes