中缀表达式转后缀表达式的栈实现
/*Name:infixSuffixConv.c Copyright: personalAuthor: hojorDate: 10-06-10 21:24Description: infix convert to suffix*/#include<stdio.h>#include<stdlib.h>#define STACK_SIZE20////~stack start//stack struct typedef struct stack{ int top; int a;}stack;//create stackstack * createStack(){ stack * s =(stack *)malloc(sizeof(stack)); s->top = -1; return s;}//get the the top value of stackint getTop(stack * s){ return s->a;}//is stack empty?int isEmpty(stack * s){ return s->top == -1;}//is stack full?int isFull(stack * s){ return s->top == (STACK_SIZE-1);}//pop stack return valueint pop(stack * s){ if(!isEmpty(s)) { return s->a; } else { printf("stack empty!!\n"); return 0; }}//push value x to stackvoid push(stack * s,int x){ if(!isFull(s)) { s->a[++s->top] = x; } else { printf("stack is full!!\n"); }}////~////~infix suffix convert start//get the level of symbolint getLevel(char symbol){ switch(symbol) { case '(': return 10; break; case '*': case '/': return 9; break; case '+': case '-': return 8; break; default: printf("symbol error!!:[%c]\n",symbol); } }//is char symbol??int isSymbol(char ch){ return (ch == '(')||(ch == '*')||(ch == '/') \ ||(ch == '-')||(ch == '+')||(ch == ')');}//function of convert infix to suffixvoid infix_suffix_convert(char * infixStr,char * suffixStr){ stack * symStack = createStack(); int iCount = strlen(infixStr),i,flag,j,k,n; i=j=k=flag=n=0; for(i=0;i<=iCount;i++) { //表达式中读到字符为运算符 if(isSymbol(infixStr)) { /*符号入栈条件,如果当前读取的符号不是闭合括号，并且栈为空或栈顶 为开括号或栈顶的符号优先级小于当前读取符号则符号入栈*/ if((isEmpty(symStack) && \ infixStr != ')' ) || ( (char)getTop(symStack)=='(' && \ infixStr != ')' ) || ( infixStr!=')' && \ getLevel((char)getTop(symStack)) < getLevel(infixStr) )) { push(symStack,infixStr); } else if(infixStr == ')') {/*如果遇到闭合括号，符号出栈，输出，直到开括号出栈为止*/ while((char)getTop(symStack)!='(') { sprintf(suffixStr,"%s %c",suffixStr,pop(symStack)); } pop(symStack); } else {/*如果栈为非空并且栈顶符号优先级大于当前读取的符号则出栈， 输出，直到栈顶符号的优先级小于当前读取的符号为止*/ while(!isEmpty(symStack) && (getLevel((char)getTop(symStack)) \ >= getLevel(infixStr)) ) { sprintf(suffixStr,"%s %c",suffixStr,pop(symStack)); } push(symStack,infixStr); } flag=2; } else if(infixStr>='0' && infixStr<='9') {//表达式中读取的字符为数字，输出 if(flag == 2 || flag == 0) { sprintf(suffixStr,"%s %d",suffixStr,atoi(&infixStr)); flag = 3; } } else { ; } } //因数字已经全部输出，故栈内所有符号出栈，输出 while(!isEmpty(symStack)) sprintf(suffixStr,"%s %c",suffixStr,pop(symStack)); }////~int main(){ ///---stack test printf("\n********** stacktest ***********\n"); int i,j=0,k=0; stack * s = createStack(); for(i=0;i<10;i++) push(s,i); for(i=0;i<10;i++) printf("%d ",pop(s)); putchar('\n'); free(s); ///---convert start printf("\n********* convert start **********\n"); int a = 50; char * infix="( 177 + 25 ) * 555 + (35 + 655 )"; printf("\n中缀表达式:\n%s\n",infix); char suffix; memset(suffix,0,sizeof(suffix)); infix_suffix_convert(infix,suffix); printf("\n后缀表达式:\n%s\n\n",suffix); system("pause"); return 0;}
页:
[1]