中缀表达式转换为后缀表达式

[!Tip]

本节源代码见Github链接🔗

问题描述

使用栈来实现将中缀表达式转换为后缀表达式 中缀表达式：中缀表达式由一个单一字符或运算符，连接前后两个中缀字符串共同组成。如：(A+B)+(C-D) 前缀表达式：前缀表达式由一个单一字符或运算符，随后是两个前缀字符串共同组成。每个前缀字符串长度大于1，包含一个运算符、第一个操作数和第二个操作数。如：++AB-CD 后缀表达式：后缀表达式（逆波兰表达式）由两个后缀字符串，随后是一个单一字符或运算符共同组成。每个后缀字符串长度大于1，包含第一个操作数和第二个操作数，随后是一个运算符。如：AB+CD-+

核心思路

1. 维护运算符之间的优先级关系；
2. 创建栈；
3. 遍历表达式字符串，并进行判断：
   1. 如果是操作数，则直接输出，不入栈；
   2. 如果是右括号")"，则弹出栈内元素，直到一个左括号"("出栈
   3. 如果是一个运算符或左括号"("，则入栈，直至出现一个优先级更小的符号，或者出现一个左括号
4. 出栈并输出元素，直至栈空 （栈中仅存储运算符和左括号'('，由于后缀表达式中不包含括号，所以输出后缀表达式时将不输出括号）

实现代码

时间复杂度

时间复杂度为O(n)，用于扫描长度为n的链表。

空间复杂度

空间复杂度为O(1)，用于存储临时变量。