提问：编写程序，将表达式a+b*c-d/e转换成前缀表达式，输出。
网友回答：
程序的话，你要告知你要用的语言的，以下是C++的参考（常见的数据结构）
#include <iostream> #include<stdlib.h> using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREASE 10 typedef struct { char *base; char *top; int stacksize; } SqStack; int InitStack(SqStack &S) { S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S.base) { cout<<"分配空间失败!"; exit(-1); } S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 0; } int Push(SqStack &S,char e) { if((S.top-S.base)>=STACK_INIT_SIZE) { S.base=(char *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREASE)*sizeof(char)); if(!S.base) { cout<<"分配空间失败!"; exit(-1); } S.top=S.base+STACK_INIT_SIZE; S.stacksize=STACK_INIT_SIZE+STACKINCREASE; } *(S.top)=e;//结构体 S.top++; return 0; } int Pop(SqStack &S,char &e) { if(S.base==S.top) { cout<<"栈为空!"; exit(0); } S.top--; e=*(S.top); return 0; } int GetTop(SqStack &S,char &e) { if(S.base==S.top) { cout<<"栈为空!"; return 0; } else { e=*(S.top-1); return 1; } } int EmptyStack(SqStack &S) { if(S.base==S.top) return 1;//stack is empty! else return 0;//stack is not empty! } int Precede(char a,char b)//a为符号栈栈顶元素,b为待插入的元素 { int i;//i=1入栈,i=0弹出操作符以及操作数进行计算 if((a=='+'||a=='-')&&(b=='*'||b=='/')) i=1; if((a=='+'||a=='-')&&(b=='+'||b=='-')) i=0; if((a=='*'||a=='/')&&(b=='*'||b=='/')) i=0; if((a=='*'||a=='/')&&(b=='+'||b=='-')) i=0; if(a=='('||a==')') i=1; return i; } int Nifix_To_Prefix (const char *p) { char a,c,d,e; int i; SqStack S,S1,S2;//S为操作符栈,S1为存储倒置后元素的栈,S2存储的是逆序的前缀表达式，最后依次弹出以实现最终的前缀表达式 InitStack(S); InitStack(S1); InitStack(S2); //由于要从右到左依次读取表达式中的各个元素，所以这里利用一个栈S1将它们倒置 d='#'; Push(S1,d); while(*p!='#') { d=*p; Push(S1,d); p++; if(*p=='#') break; } Pop(S1,c); cout<<"转换后的前缀表达式为："<<endl; while(c!='#') { if(c>='a'&&c<='z') Push(S2,c);//表达式只支持小写 if(c==')') Push(S,c); //输入为右括号 if(c=='(')//输入为左括号 { if(!EmptyStack(S)) GetTop(S,e); while(e!=')') { Pop(S,a); Push(S2,a); if(!EmptyStack(S)) GetTop(S,e);//直到遇到左括号 if(e==')') Pop(S,e); } } if(c=='+'||c=='-'||c=='*'||c=='/') { if(EmptyStack(S)) Push(S,c); else { GetTop(S,e); i=Precede(e,c); if(i==1) Push(S,c); if(i==0) { while(!i) { Pop(S,a); Push(S2,a); if(!EmptyStack(S)) { GetTop(S,e); i=Precede(e,c); } else break; } Push(S,c); } } } Pop(S1,c); } if(!EmptyStack(S)) { while(!EmptyStack(S)) { Pop(S,a); Push(S2,a); } } while(!EmptyStack(S2)) { Pop(S2,a); cout<<a<<" "; } cout<<endl; return 0; } int main() { Nifix_To_Prefix("a+b*c-d/e#"); cout <<endl; return 0; }
结果为
