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

C++利用栈实现中缀表达式转后缀表达式 C++利用栈实现中缀表达式转后缀表达式是计算机科学中的一种常见问题，通过栈的特性可以轻松地将中缀表达式转换为后缀表达式。在这篇文章中，我们将详细介绍如何使用C++语言实现中缀表达式转换为后缀表达式的过程。 让我们来了解中缀表达式和后缀表达式的概念。中缀表达式是一种常见的数学表达式形式，如1+(2-3)*4+10/5，它的特点是运算符号位于数字之间。后缀表达式则是一种逆波兰记法的表示形式，例如1 2 3 - 4 * + 10 5 /，它的特点是运算符号位于数字之后。 下面我们将详细介绍如何使用栈来实现中缀表达式转换为后缀表达式。整个过程可以分为以下七步： Step1：遇到数字1，直接输出。 Step2：遇到符号“+”，入栈。 Step3：遇到符号“(”，入栈，接着是数字2，输出，然后是符号“-”，入栈。 Step4：遇到数字3，输出，紧跟着是“)”，此时，我们需要去匹配栈里的“(”，然后再匹配前将栈顶数据依次出栈。 Step5：遇到符号“*”，直接入栈。 Step6：遇到数字4，输出，之后是符号“+”，此时栈顶元素是符号“*”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加号要大，所以出栈。 Step7：最后一个数字5，输出，所有的输入处理完毕，但是栈中仍然有数据，所以将栈中符号依次出栈。 总结规则：从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将低优先级的那个符号入栈。 下面是实现该算法的C++代码： ```c #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; void 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; } void 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++; } void 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); } } // ... } return 0; } ``` 通过上面的代码，我们可以轻松地将中缀表达式转换为后缀表达式。这个算法的时间复杂度为O(n)，其中n是中缀表达式的长度。空间复杂度为O(n)，其中n是栈的最大深度。 使用栈来实现中缀表达式转换为后缀表达式是一种高效且简洁的方法，它广泛应用于编译器、解释器和计算器等领域。