利用栈实现：中缀表达式转后缀表达式

全栈程序员-站长 • 2025年11月30日上午10:15 • 未分类 • 阅读 3

题目：现有中缀表达式如：1+(2-3)*4+10/5

请用栈的特性编写一个程序，使得程序输出后缀表达式

分析如下：

STEP1：

1+(2-3)*4+10/5

STEP2：

1+(2-3)*4+10/5

第三个字符是“(”，依然是符号，入栈，接着是数字2，输出，然后是符号“-”，入栈：

利用栈实现：中缀表达式转后缀表达式

STEP3：

1+(2-3)*4+10/5

STEP4：

1+(2-3)*4+10/5

紧接着是符号“*”，直接入栈

利用栈实现：中缀表达式转后缀表达式

STEP5：

1+(2-3)*4+10/5

最后把刚刚的那个加号入栈，操作如下图：

利用栈实现：中缀表达式转后缀表达式

STEP6：

1+(2-3)*4+10/5

紧接着数字10，输出，最后是符号“/”，进栈：

利用栈实现：中缀表达式转后缀表达式

STEP7：

1+(2-3)*4+10/5

最后一个数字5，输出，所有的输入处理完毕，但是栈中仍然有数据，所以将栈中符号依次出栈。

总结规则：

从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将低优先级的那个符号入栈

代码实现如下：

#include <stdio.h> #include <stdlib.h> #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } Push(sqStack *s, ElemType e) { // 栈满，追加空间，鱼油必须懂！ if( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base + s->stackSize; s->stackSize = s->stackSize + STACKINCREMENT; } *(s->top) = e; // 存放数据 s->top++; } Pop(sqStack *s, ElemType *e) { if( s->top == s->base ) return; *e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针 } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; char c, e; InitStack( &s ); printf("请输入中缀表达式，以#作为结束标志："); scanf("%c", &c); while( c != '#' ) { while( c>='0' && c<='9' ) { printf("%c", c); scanf("%c", &c); if( c<'0' || c>'9' ) { printf(" "); } } if( ')' == c ) { Pop(&s, &e); while( '(' != e ) { printf("%c ", e); Pop(&s, &e); } } else if( '+'==c || '-'==c ) { if( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if( '(' == e ) { Push(&s, e); } else { printf("%c ", e); } }while( StackLen(s) && '('!=e ); Push(&s, c); } } else if( '*'==c || '/'==c || '('==c ) { Push(&s, c); } else if( '#'== c ) { break; } else { printf("\n出错：输入格式错误！\n"); return -1; } scanf("%c", &c); } while( StackLen(s) ) { Pop(&s, &e); printf("%c ", e); } return 0; }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/231638.html原文链接：https://javaforall.net