逆波兰表达式和调度场算法

Friday, April 17, 2020

逆波兰表达式

逆波兰表达式也叫后缀表达式,而我们平常使用的则是中缀表达式

中缀表达式后缀表达式
1+212+
1+2+312+3+
1+2*3123*+
3^3^3333^^

中缀表达符合人的思维和习惯,方便人阅读和理解,而后缀表达式则方便计算机处理。在逆波兰表达式中没有括号,也不需要注意运算符的优先级。计算逆波兰表达式一般基于堆栈,下面是维基百科给出的计算过程伪代码


  • while 有输入
    • 读入下一个符号X
    • IF X是一个操作数
      • 入栈
    • ELSE IF X是一个操作符
      • 有一个先验的表格给出该操作符需要n个参数
      • IF堆栈中少于n个操作数
        • (错误) 用户没有输入足够的操作数
      • Else,n个操作数出栈
      • 计算操作符。
      • 将计算所得的值入栈
  • IF栈内只有一个值
    • 这个值就是整个计算式的结果
  • ELSE多于一个值
    • (错误) 用户输入了多余的操作数

假设表达式本身没有错误的话,其实逻辑很简单

  • 遇到数字直接入栈

  • 遇到运算符,从栈中弹出所需数量的操作数,计算结果入栈(例如减法需要两个操作数,负号只需要一个,这两个符号要用不同字符表示)

  • 所有计算完成之后栈中剩余的最后一个数即为最终结果

调度场算法

计算逆波兰表达式还是很简单的,比较困难的是将一般的中缀表达式转换为逆波兰表达式,艾兹赫尔·韦伯·戴克斯特拉 (提出“GOTO有害论 ”,信号量PV原语 ,解决了“哲学家就餐问题 ”)引入了调度场算法解决这个问题。

具体算法维基百科其实讲的很明白了,详情戳这里

可能需要注意的就是运算符的左结合和有结合,解释好麻烦,直接看例子:

+ - * / 是左结合的,所以 1-2-3 相当于 (1-2)-32*3*4 相当于 (2*3)*4

^ 是右结合的,所以 3^3^3 = 3^(3^3) = 3^27 = 7625597484987 ,不注意这一点的话 (3^3)^3 = 27^3 = 19683 ,答案差距还是相当大的

下面是我用Lua给fcitx5写的一个简易计算器的部分代码,仅处理了 + - * / ^ ~ (负号)

function shunting_yard(input)
    -- 事先已经把用户输入的算式按操作数和运算符分割为一个个字符串,
    -- 所以input其实是一个表
    -- 负号已经处理成~
    -- 无效符号已经删除
    
    -- 用一张表记录各运算符的优先级,#标记栈底
    local priority = {}
    priority["#"] = 0
    priority["+"] = 1
    priority["-"] = 1
    priority["~"] = 2
    priority["*"] = 2
    priority["/"] = 2
    priority["^"] = 3

    local stack = {"#"}
    local output = {}

    for i=1, #input do
        local tmp = input[i]
        if tonumber(tmp) then -- 数字直接入栈
            table.insert(output, tmp)
        elseif tmp == '(' then -- 左括号直接入栈
            table.insert(stack, tmp)
        elseif tmp == ')' then -- 右括号则不断出栈,直到遇到'('
            while stack[#stack] ~= '(' do
                table.insert(output, table.remove(stack))
            end
            table.remove(stack)
        elseif tmp == '^' then -- 右结合运算符
            while priority[stack[#stack]] ~= nil 
				and priority[tmp] < priority[stack[#stack]]
            do
                table.insert(output, table.remove(stack))
            end
            table.insert(stack, tmp)
        else
            -- 左结合运算符
            while priority[stack[#stack]] ~= nil 
            	and priority[tmp] <= priority[stack[#stack]]
            do
                table.insert(output, table.remove(stack))
            end
            table.insert(stack, tmp)
        end
    end


    -- 弹出栈中剩余运算符到输出队列
    while #stack > 1 do
            table.insert(output, table.remove(stack))
    end
    
    return output
end

至于为什么要给一个输入法框架写个计算器脚本,呃,Just For Fun😀


参考:

algorithm

C 和 Lua 取模运算的异同

Linux图形化身份认证