一. 概念
前缀表达式:+AB
中缀表达式:A+B
后缀表达式:AB+
二. 中缀转后缀算法思想
三. 代码实现
eg:
中缀表达式:[ ( A + B ) * C ] - [ E -F ]
中缀转前缀:- * + A B C - E F
中缀转后缀:A B + C * E F - -
void InfixToSuffix(char *Suffix)//栈的中缀转后缀 { Stack S=InitStack(); int i=0,k=0; ElemType x; char Infix[15]={'(','(','A','+','B',')','*','C',')','-','(','E','-','F',')'},ch; for(;i<15;i++) { ch=Infix[i]; if(ch>=65&&ch<=97) { Suffix[k]=ch;// 字母直接加入后缀表达式 k++; } else if(ch=='(') { PushStack(&S,ch);// '('直接入栈 } else if(ch==')') { while(1) { PopStack(&S,&x); Suffix[k]=x; k++; if(GetTop(S)=='(') { PopStack(&S,&x); break; } } } else if(ch=='+'||ch=='-'||ch=='*'||ch=='/') { if(StackEmpty(S)||GetTop(S)=='(') { PushStack(&S,ch);//栈空或者栈顶为'(',把运算符入栈 } else if((ch=='*'||ch=='/')&&(GetTop(S)=='+'||GetTop(S)=='-')) { PushStack(&S,ch); } else { PopStack(&S,&x); while(1) { if(((ch=='*'||ch=='/')&&(GetTop(S)=='+'||GetTop(S)=='-'))&&GetTop(S)=='(') { break; } else { PopStack(&S,&x); } } } } }
#include <stdio.h> #define MaxSize 50 #define TRUE 1 #define FALSE 0 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int top; }Stack; Stack InitStack();//初始化空栈,top=-1 int StackEmpty(Stack S);//判断栈是否为空 int PushStack(Stack *p,ElemType x);//进栈 int PopStack(Stack *p,ElemType *x);//出栈 ElemType GetTop(Stack S);//读栈顶元素 void InfixToSuffix(char *Suffix);//栈的中缀转后缀 int main() { char Suffix[15]; InfixToSuffix(Suffix); printf("后缀表达式为: "); for(int i=0;i<15;i++) { printf("%c ",Suffix[i]); } printf(" "); return 0; } void InfixToSuffix(char *Suffix)//栈的中缀转后缀 { //Infix为中缀,Suffix为后缀 Stack S=InitStack(); int i=0,k=0; ElemType x; char Infix[15]={'(','(','A','+','B',')','*','C',')','-','(','E','-','F',')'},ch; for(;i<15;i++) { ch=Infix[i]; if(ch>=65&&ch<=97) { Suffix[k]=ch;// 字母直接加入后缀表达式 k++; } else if(ch=='(') { PushStack(&S,ch);// '('直接入栈 } else if(ch==')') { while(1) { PopStack(&S,&x); Suffix[k]=x; k++; if(GetTop(S)=='(') { PopStack(&S,&x); break; } } } else if(ch=='+'||ch=='-'||ch=='*'||ch=='/') { if(StackEmpty(S)||GetTop(S)=='(') { PushStack(&S,ch);//栈空或者栈顶为'(',把运算符入栈 } else if((ch=='*'||ch=='/')&&(GetTop(S)=='+'||GetTop(S)=='-')) { PushStack(&S,ch); } else { PopStack(&S,&x); while(1) { if(((ch=='*'||ch=='/')&&(GetTop(S)=='+'||GetTop(S)=='-'))&&GetTop(S)=='(') { break; } else { PopStack(&S,&x); } } } } } while(!StackEmpty(S)) { PopStack(&S,&x); Suffix[k]=x; k++; } } Stack InitStack() { Stack S; S.top=-1; return S; } int StackEmpty(Stack S) { if(S.top==-1) { return TRUE; } else { return FALSE; } } int PushStack(Stack *p,ElemType x) { if(p->top==MaxSize-1) { printf("栈满! "); return FALSE; } p->data[++p->top]=x;//指针先加1,再入栈 return TRUE; } int PopStack(Stack *p,ElemType *x) { if(p->top==-1) { printf("栈空! "); return FALSE; } *x=p->data[p->top--];//先出栈,指针再减1 return TRUE; } ElemType GetTop(Stack S) { if(S.top==-1) { printf("栈空!无法读取栈顶元素! "); } else { return S.data[S.top]; } }
运行示例: