#include
#include
using namespace std;
string RPN;
typedef struct SNode{
struct SNode *top;
char ch;
struct SNode *next;
}*StackList;
typedef StackList operators;
void InitStack(operators &P){
SNode *node=(SNode*)malloc(sizeof(SNode));
node->top=NULL;
node->ch='#';
node->next=NULL;
P->top=node;
}
void PushStack(operators &P,char &ch){
SNode *node=(SNode*)malloc(sizeof(SNode));
node->top=NULL;
node->ch=ch;
node->next=P->top;
P->top=node;
cout<<"Push:"<
void PopStack(operators &P,char &ch){
ch=P->top->ch;
P->top=P->top->next;
cout<<"Pop:"<
void PrintStack(operators &P){
char ch='\0';
while(P->top->ch!='#'){
PopStack(P,ch);
RPN+=ch;
}
cout<
int priority(char &ch){
switch(ch){
case '^':
return 5;
case '(':
return 4;
case ')':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
case '#':
return -1;
default:
return 0;
}
}
void PushPop(operators &P,char &ch){
char temp=P->top->ch;
if(temp=='#')
PushStack(P,ch);
else{
if(priority(temp)>priority(ch)){
PopStack(P,temp);
PushStack(P,ch);
PushStack(P,temp);
cout<<"temp:"<
if(priority(temp)==priority(ch))
{
//PopStack(P,temp);
//RPN+=temp;
PushStack(P,ch);
}
if(priority(temp)
}
}
void convert(operators &P,char &ch){
switch(priority(ch)){
case 5://^
case 4://(
case 3://)
case 2://*/
PushPop(P,ch);
break;
case 1://+-
PushPop(P,ch);
break;
case 0:
RPN+=ch;
break;
}
}
int main(){
operators P=(operators)malloc(sizeof(operators));
P->top=NULL;
P->ch=NULL;
P->next=NULL;
InitStack(P);
string str;
char ch='\0';
cout<<"请输入中缀表达式:"<
for(short i=0;i
if(ch==' ')
continue;
convert(P,ch);
}
PrintStack(P);
return 0;
}
改成这样就好了。
这个程序主要是在判断运算符优先级的时候出栈入栈有错误。
请看下下面的分析:
要先设置一个运算符的栈st,从左只有扫描中缀表达式
1、如果遇到数字,直接放到后缀表达式尾;
2、如果遇到遇到运算符
a:若此时站空,则直接入栈;
b:循环:若栈st不空且栈顶运算符的优先级大于等于当前的运算符,则栈顶运算符出栈,置于后缀表达式尾;
c:若栈st不空且栈顶运算符的优先级小于当前的运算符,则将此运算符直接入栈;
反复执行1,2,知道整个中缀表达式扫描完毕,若此时栈st不空,则将栈顶的运算符依次出栈,依次置于后缀表达式尾。