提问：编写程序，将表达式a+b*c-d/e转换成前缀表达式，输出。
网友回答：
程序的话，你要告知你要用的语言的，以下是C++的参考（常见的数据结构）
#include
#include
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<<"转换后的前缀表达式为："<='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<结果为
