中缀表达式转后缀表达式(逆波兰表达式)
op | # | ( | + , - | *,/ | ) |
---|
icp | 0 | 6 | 4 | 2 | 1 |
isp | 0 | 1 | 5 | 3 | 6 |
思路
假设表达式为string ex =" a+(b-c)*d"
将表达式处理为 "a+(b-c)*d#" 以#做末尾标识,
初始时 栈s 中放入一个 # ,int i=0;
icp表示表达式当前扫描项的字符的优先级,isp表示栈顶操作符的优先级 ,优先级表如上
当 栈非空 或 当前扫描项 ex [i]不是 # 时执行以下操作
1) if ex非操作符,直接输出,i++;
2)else if ex为操作符,则
if icp>isp, ex[i]入栈
else if icp<isp 一直出栈,直到icp >=isp
else if icp == isp //此时为( ) 或 #
将栈顶元素出栈,读取下一元素
#include <iostream>
#include <string>
#include<stack>
using namespace std;
stack<char> s;
int icp(char ch)
{
int pr;
switch (ch)
{
case '#':
pr = 0;
break;
case '(':
pr = 6;
break;
case '*':
case '/':
pr = 4;
break;
case '+':
case '-':
pr = 2;
break;
case ')':
pr = 1;
break;
}
return pr;
}
int isp(char ch)
{
int pr;
switch (ch)
{
case '#':
pr = 0;
break;
case '(':
pr = 1;
break;
case '*':
case '/':
pr = 5;
break;
case '+':
case '-':
pr = 3;
break;
case ')':
pr = 6;
break;
}
return pr;
}
void polish(string a) {
s.push('#');
int i = 0;
while (!s.empty() ||a[i]!='#' ){
if (a[i] >= 'a' && a[i] <= 'z')
cout << a[i++] << " ";
else
{
int com = icp(a[i]) - isp(s.top());
if (com>0)
{
s.push(a[i++]);
}
else if (com==0)
{
if (a[i] != '#')
i++;
s.pop();
}
else if (com<0)
{
cout << s.top() << " ";
s.pop();
}
}
}
};
int main()
{
string str;
cin >> str;
str = str + "#";
polish(str);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)