美文网首页
逆波兰式

逆波兰式

作者: 深耕项目管理 | 来源:发表于2017-12-20 00:17 被阅读0次

    逆波兰式,是编程计算四则运算结果的算法。例子:平时写法a+b(中缀表达式),逆波兰式ab+。
    把中缀表达式编程后缀表达式的法则:
    首先需要两个栈:s1操作数栈,s2运算符栈。当前取的字符为x。
    a.如果x是数字,直接压入s1.
    b.如果x是左括号,直接压入s2.
    c.如果x是右括号,把它和距离栈顶最近的左括号之前的运算符,依次压入操作数栈。左括号舍弃。
    d.如果x是+-*/。如果栈顶是左括号,直接压入s2。否则,如果s2栈顶运算符优先级低于x(不包括等于),x压入s2.否则,依次弹出栈顶,压入s1,直到满足条件为止。
    e.重复以上四条。

    例子:计算9+(3-1)*3+10/2
    s1: 栈底栈顶
    s2:栈底栈顶

    x=9
    s1: 栈底9栈顶
    s2:栈底栈顶
    x=+
    s1: 栈底9栈顶
    s2:栈底+栈顶
    x=(
    s1: 栈底9栈顶
    s2:栈底+(栈顶
    x=3
    s1: 栈底93栈顶
    s2:栈底+(栈顶
    x=-
    s1: 栈底93栈顶
    s2:栈底+(-栈顶
    x=1
    s1: 栈底931栈顶
    s2:栈底+(-栈顶
    x=)
    s1: 栈底931栈顶
    s2:栈底+(-栈顶
    -从s2弹出,压入s1.
    s1: 栈底931-栈顶
    s2:栈底+栈顶
    s1中出现运算符,要计算
    s1: 栈底92栈顶
    s2:栈底+栈顶
    x=*
    s1: 栈底92栈顶
    s2:栈底+栈顶
    x=3
    s1: 栈底923栈顶
    s2:栈底+
    栈顶
    x=+
    把=依次从s2弹出压入s1
    s1: 栈底923
    栈顶
    s2:栈底+栈顶

    s1: 栈底96栈顶
    s2:栈底+栈顶

    s1: 栈底96+栈顶
    s2:栈底栈顶

    s1: 栈底15栈顶
    s2:栈底+栈顶

    x=10

    s1: 栈底15 10栈顶
    s2:栈底+栈顶

    x=/
    s1: 栈底15 10栈顶
    s2:栈底+/栈顶

    x=2
    s1: 栈底15 10 2栈顶
    s2:栈底+/栈顶

    最后,s2依次出栈,压入s1
    s1: 栈底15 5栈顶
    s2:栈底+栈顶
    s1: 栈底20栈顶
    s2:栈底栈顶

    写在最后的话:知识要弄懂,再简单也要下苦工。

    相关文章

      网友评论

          本文标题:逆波兰式

          本文链接:https://www.haomeiwen.com/subject/oydwwxtx.html