原表达式转换成后缀表达式——表达式求值问题

#include"suffix.h" int initList(SqList &l) { //构造一个空的线性表l l.listbase=(elemType *)malloc(LIST_INIT_SIZE * sizeof(elemType)); if(!l.listbase) { exit(-1); } l.length=0; l.listsize=LIST_INIT_SIZE; return 0; } void listInsert(SqList &l) { char ch; int w; int i=0; /*while(l.length<7) { printf("请输入运算符："); scanf("%c", &ch); printf("请输入%c的权值：", ch); scanf("%d", &w); getchar(); l.listbase[i].op=ch; l.listbase[i].weight=w; l.length++; i++; }*/ l.length=7; l.listbase[0].op='#'; l.listbase[0].weight=-1; l.listbase[1].op='('; l.listbase[1].weight=0; l.listbase[2].op=')'; l.listbase[2].weight=0; l.listbase[3].op='+'; l.listbase[3].weight=1; l.listbase[4].op='-'; l.listbase[4].weight=1; l.listbase[5].op='*'; l.listbase[5].weight=2; l.listbase[6].op='/'; l.listbase[6].weight=2; } void display(SqList l) { for(int i=0; i<l.length; i++) { printf("运算符%2c的权值为：%3d", l.listbase[i].op, l.listbase[i].weight); printf("\n"); } } int locate(SqList l, char ch, int (* fun)(char, char)) { //在顺序线性表中查找第一个值与ch满足fun()的元素的下标 //若找到，则返回其在线性表中的下标，否则返回-1 int i=0;//i的初值为第一个元素的下标 while((i<l.length) && !(* fun)(l.listbase[i].op, ch)) { i++; } if(i<l.length) { return i; } else { return -1; } } int compare(char a, char b) { return (a==b)? 1: 0; } //顺序栈类型的定义 void initStack(stack &s) { s.stackbase=(char *)malloc(STACK_INIT_SIZE * sizeof(char)); if(!s.stackbase)//存储空间分配失败 { exit(1); } s.stacksize=STACK_INIT_SIZE; s.top=0;//空栈的栈顶指针为0 } bool getTop(stack s, char &e) { //若栈不空，则用e返回栈顶元素，并返回true; //否则返回false if(s.top == 0) { return false; } e=*(s.stackbase+s.top-1);//返回非空栈中栈顶元素 return true; } bool push(stack &s, char e) { //若栈的存储空间不满，则插入元素e， //e为新的栈顶元素，并返回true; if(s.top == s.stacksize)//栈已满 { char * newbase; newbase=(char *)realloc(s.stackbase, (s.stacksize+STACKINCREMENT)*sizeof(char)); if(!newbase) { exit(1); } s.stackbase=newbase; s.stacksize+=STACKINCREMENT; } *(s.stackbase+s.top)=e;//插入新元素 s.top++;//栈顶指针后移 return true; } bool pop(stack &s, char &e) { //若栈不空，则删除栈顶元素，用e返回其值， //并返回true；否则返回false if(s.top == 0) { return false; } e=*(s.stackbase+s.top-1);//返回非空栈中栈顶元素 s.top--;//栈顶指针前移 return true; } void transform(char suffix[], char exp[], SqList l) { //从合法的表达式字符串exp求得其相应的后缀式suffix stack s; initStack(s); push(s, '#'); char * p; p=exp; char ch=* p; int i=0; char e; int loc; while(s.top!=0) { loc=locate(l, ch, compare); if(loc == -1) { suffix[i++]=ch; } else { switch(ch) { case '(': push(s, ch); break; case ')': { pop(s, e); while(e != '(') { suffix[i++]=e; pop(s, e); } break; } default: { int s1; int s2=locate(l, ch, compare); //loc int flag=1; while(flag) { getTop(s, e); s1=locate(l, e, compare); if(l.listbase[s1].weight>l.listbase[s2].weight) { pop(s, e); suffix[i++]=e; } else { flag=0; } }//while(flag) if(ch != '#') { push(s, ch); } break; }//default }//switch }//else if(ch != '#') { p++; ch=* p; } else { suffix[i]=ch; break; } }//while }//transform