学生一枚,求帮助,看看我这个中缀转前缀的程序
中缀转前缀.zip
(1.96 KB)
#include<iostream> using namespace std; #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<string.h> #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType; typedef struct { SElemType *top; SElemType *base; int Stacksize; }SqStack; int InitStack(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) { exit(OVERFLOW); } S.top=S.base; S.Stacksize=STACK_INIT_SIZE; return OK; } int Gettop(SqStack S,SElemType &e) //除了引用也可以用返回函数值得方式返回e {//如果栈不空,则返回栈顶元素,并返回OK; if(S.base==S.top) { return ERROR; } e=*(S.top-1); return OK; } int push(SqStack &S,SElemType e) { if((S.top-S.base)>=S.Stacksize) //栈满,追加存储空间 { S.base=(SElemType *)realloc(S.base,(S.Stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) { exit(OVERFLOW); } S.Stacksize+=S.Stacksize+STACKINCREMENT; S.top=S.base+S.Stacksize; } *(S.top)++=e; return OK; } int pop(SqStack &S,SElemType &e) { if(S.base==S.top) { return ERROR; } e=*(--S.top); return OK; } int isoperator(SElemType c)//判断是否为操作符,如果是则返回ture. { switch(c) //也可以用if语句 { case '+': case '-': case '*': case '/':return OK; default :return ERROR; } } int level(SElemType op)//操作符的优先级初始化 { //方便入栈时候的比较 int level; switch(op) { case '+': case '-':level=1; case '*': case '/':level=2; default:level=0; return level; } } string mid_to_pre(string s) //将一个中缀串转换为后缀串 { int i; SElemType e,b; SqStack pre; InitStack(pre); //建立存放逆序前前缀表达式的栈 string output=""; //输出串 for(i=sizeof(s)-1;i>=0;) //从右向左扫描 { if(s[i]>=48&&s[i]<=57) //字符之间用ascii码比较 { output=output+s[i]; //假如是操作数则直接进输出串 } if(s[i]==')') //如果是右括号直接压栈 { push(pre,s[i]); } while(isoperator(s[i]))//如果是运算符,执行运算符的相关操作 { Gettop(pre,e);//获取栈顶元素 if(pre.top==pre.base)//如果栈空,运算符直接进栈 { push(pre,s[i]); } else if(e==')') //如果栈顶元素为右括号直接入栈 { push(pre,s[i]); } else if(level(s[i])>=level(e))//如果它的优先级高于或等于栈顶运算符,此运算符入栈 { push(pre,s[i]); } else { pop(pre,b); output=output+b; } } if(s[i]=='(')//假如是左括号,栈中运算符逐个出栈并输出,知道遇到左括号位置,左括号出战 { while(e!=')') { pop(pre,b); output=output+b; Gettop(pre,e); } pop(pre,b); } i--; //假如输入还没完毕,跳转到步骤二 } while(pre.base!=pre.top) { pop(pre,b); output=output+b; } return output; } int main() { int i; string input,output; printf("请输入串:\n"); cin>>input; output=mid_to_pre(input);//中缀转前缀(还差一步逆序,可以在子函数再增设一字符串) printf("前缀表达式为:\n"); for(i=sizeof(output)-1;i>=0;i++)//求串的逆序后才会变成真正的前缀 { printf("%c",output[i]); } printf("\n"); return 0; }