sketches/shunting_yard.lua

   1
   2 require "pp"
   3 require "bootstrap/rtn"
   4
   5 -- http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
   6
   7 function get_primary(text)
   8   if text:match("%(") then
   9     text:consume_pattern("%(")
  10     local prim = parse(text)
  11     text:consume_pattern("%)")
  12     return prim
  13   elseif text:match("%d") then
  14     return text:consume_pattern("%d")
  15   else
  16     return nil
  17   end
  18 end
  19
  20 Binary = {}
  21 Unary = {}
  22
  23 binop_prec = {["+"]=1, ["-"]= 1, ["*"]=2, ["/"]=2}
  24 unop_prec = {["-"]=3, ["+"]=3}
  25 binop_assoc = {["+"]="left", ["-"]="left", ["*"]="left", ["/"]="left"}
  26
  27 function get_operator(text)
  28   if text:match("[+-/*]") then
  29     return {Binary, text:consume_pattern("[+-/*]")}
  30   else
  31     return nil
  32   end
  33 end
  34
  35 function get_unary_operator(text)
  36   if text:match("[+-]") then
  37     return {Unary, text:consume_pattern("[+-]")}
  38   else
  39     return nil
  40   end
  41 end
  42
  43 function is_binary(op)
  44   return op[1] == Binary
  45 end
  46
  47 function op_greater(op1, op2)
  48   op1_type, op1_op = unpack(op1)
  49   op2_type, op2_op = unpack(op2)
  50   if op2_type == Unary then
  51     return false
  52   elseif op1_type == Unary then
  53     if unop_prec[op1_op] >= binop_prec[op2_op] then
  54       return true
  55     else
  56       return false
  57     end
  58   elseif binop_prec[op1_op] > binop_prec[op2_op] or
  59          (binop_prec[op1_op] == binop_prec[op2_op] and binop_assoc[op1_op] == "left") then
  60     return true
  61   else
  62     return false
  63   end
  64 end
  65
  66 function parse(text)
  67   local operators = {}
  68   local operands = {}
  69   parse_term(text, operators, operands)
  70   local operator = get_operator(text)
  71   while operator do
  72     push_operator(operator, operators, operands)
  73     parse_term(text, operators, operands)
  74     operator = get_operator(text)
  75   end
  76
  77   while #operators > 0 do
  78     pop_operator(operators, operands)
  79   end
  80   return operands
  81 end
  82
  83 function parse_term(text, operators, operands)
  84     local unary_op = get_unary_operator(text)
  85     while unary_op do
  86       push_operator(unary_op, operators, operands)
  87       unary_op = get_unary_operator(text)
  88     end
  89     table.insert(operands, get_primary(text))
  90 end
  91
  92 function push_operator(operator, operators, operands)
  93   while #operators > 0 and op_greater(operators[#operators], operator) do
  94     pop_operator(operators, operands)
  95   end
  96   table.insert(operators, operator)
  97 end
  98
  99 function pop_operator(operators, operands)
 100   local operator = table.remove(operators)
 101   if is_binary(operator) then
 102     local o2 = table.remove(operands)
 103     local o1 = table.remove(operands)
 104     table.insert(operands, {operator[2], o1, o2})
 105   else
 106     table.insert(operands, {operator[2], table.remove(operands)})
 107   end
 108 end
 109
 110 text = CharStream:new("-2+3*-(3+4)")
 111 text:ignore("whitespace")
 112 print(serialize(parse(text)))
 113