P1175 表达式的转换

题目描述

给定一个中缀表达式，将其转换为后缀表达式。

输入格式

共一行，为一个长度不超过 100 的字符串，表示中缀表达式，表达式中可能包含+、-、*、/、(、)这些字符，保证表达式合法。

输出格式

共一行，为转换后的后缀表达式，每个数字和符号之间用一个空格隔开。

数据范围

输入样例：

2+3*(7-4)+8/4

输出样例：

2 3 7 4 - * + 8 4 / +

算法

(栈)

栈是一种后进先出的数据结构，通常用数组模拟实现。本题中，我们可以维护一个栈，用于存储运算符号。在遍历中缀表达式时，依次处理每个字符。如果遇到数字，则直接输出；如果遇到运算符，则有不同的处理方式：

如果栈为空，则将运算符入栈；
如果栈不为空，则比较栈顶运算符和当前运算符的优先级。如果当前运算符优先级较高，则将其入栈；否则将栈顶运算符出栈，直到栈顶运算符优先级小于等于当前运算符，然后将当前运算符入栈；
如果遇到左括号，则将其入栈；
如果遇到右括号，则将栈中的运算符依次出栈，直到遇到第一个左括号。

时间复杂度

遍历中缀表达式，时间复杂度为O(n)。由于我们需要用栈来存储运算符，因此空间复杂度也为O(n)。

C++ 代码

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/convert-expression/solution/biao-da-shi-de-zhuan-huan-by-leetcode-7orrs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。