C语言编程 |
您所在的位置：网站首页 › c语言运算符的先后顺序 › C语言编程 |
C语言编程
|
1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一： 遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。 情况二： 遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。 情况三： 遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。（因为左括号要匹配右括号时才弹出）。 情况四：获取完后，将栈中剩余的运算符号依次弹栈输出 例：将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 + 转换算法代码如下： /*中缀转后缀函数*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储 的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左 括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止 左括号只弹出不打印（右括号也不压栈）*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括号都是优先级高的，直接压栈*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n输入格式错误！\n"); return ; } i++; } /*最后把栈中剩余的运算符依次弹栈打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } }完整代码如下： #include #include #include #include #define INITSIZE 20 #define INCREMENT 10 #define MAXBUFFER 20 #define LEN sizeof(Elemtype) /*栈的动态分配存储结构*/ typedef char Elemtype; typedef struct{ Elemtype *base; Elemtype *top; int StackSize; }SqStack; /*初始化栈*/ void InitStack(SqStack *S) { S->base=(Elemtype*)malloc(LEN*INITSIZE); assert(S->base !=NULL); S->top=S->base; S->StackSize=INITSIZE; } /*压栈操作*/ void PushStack(SqStack *S,Elemtype c) { if(S->top - S->base >= S->StackSize) { S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT)); assert(S->base !=NULL); S->top =S->base+S->StackSize; S->StackSize+=INCREMENT; } *S->top++ = c; } /*求栈长*/ int StackLength(SqStack *S) { return (S->top - S->base); } /*弹栈操作*/ int PopStack(SqStack *S,Elemtype *c) { if(!StackLength(S)) { return 0; } *c=*--S->top; return 1; } /*中缀转后缀函数*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储 的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左 括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止 左括号只弹出不打印（右括号也不压栈）*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括号都是优先级高的，直接压栈*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n输入格式错误！\n"); return ; } i++; } /*最后把栈中剩余的运算符依次弹栈打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } } int main() { Elemtype str[MAXBUFFER]; SqStack S; gets(str); Change(&S,str); return 0; }运行效果截图如下： |
【本文地址】
今日新闻 |
推荐新闻 |