【数据结构】栈_中缀表达式转后缀表达式
中缀表达式转后缀表达式过程:
非符号元素输出
栈存储符号
将要入栈的元素级别高于栈顶元素,则入栈
将要入栈的元素级别低于或者等于栈顶元素,栈顶元素出栈,直到级别大于栈顶元素
右括号成为栈顶元素时,栈中元素依次出栈,知道左括号出栈完成(括号不输出)
【例题】【全国联考2014年】
- 假设栈初始为空,将中缀表达式a/b+(cd-ef)/g转换为等价的后缀表达式的过程中,当扫描到f时,栈中的元素依次是+(-*
解析如下:
扫描到a为非符号元素,输出a
扫描到 / 为符号元素,入栈
扫描到 + ,级别低于 / , /出栈,此时栈为空,+入栈
扫描到 ( ,入栈
扫描到 c 输出 c
扫描到 * ,级别高于 + ,入栈
扫描到 d,输出d
扫描到 - ,级别低于 * ,*出栈 ,此时栈顶元素是( , - 入栈
扫描到 e ,输出 e
扫描到 * ,级别高于 - ,*入栈
扫描到 f,输出 f
此时栈内元素依次是+(-*
松柏兄好厉害