中缀表达式转后缀表达式

[编程题]中缀表达式转后缀表达式

热度指数：2111 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

将中缀表达式转为后缀表达式，输入 a+b*c/d-a+f/b 输出 abc*d/+a-fb/+
要求：语言不限；输入输出均为单个字符串；操作数用单个小写字母表示，操作符只需支持 +-*/，按照四则运算顺序确定优先级，不包含括号

输入描述:

一个字符串为合法的中缀表达式
字符串长度不超过200000

输出描述:

对应的后缀表达式

示例1

输入

a+b*c/d-a+f/b

输出

abc*d/+a-fb/+

算法知识视频讲解

Python

ElonB

""""
栈，判断运算优先级
"""
if __name__ == "__main__":
    s = input().strip()
    t_ans, t_opt = [], []
    for i in range(len(s)):
        if s[i] in '+-':
            while t_opt and len(t_ans) >= 2:
                x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
                t_ans.append(y + x + opt)
            t_opt.append(s[i])
        elif s[i] in '*/':
            if t_opt and t_opt[-1] in '*/' and len(t_ans) >= 2:
                x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
                t_ans.append(y + x + opt)
            t_opt.append(s[i])
        else:
            t_ans.append(s[i])
    while t_opt and len(t_ans) >= 2:
        x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
        t_ans.append(y + x + opt)
    print(t_ans[0])

发表于 2019-07-17 17:34:37 回复(0)