使用栈和后缀表达式解析算术表达式

最近补习数据结构（谁叫我不是科班出身呢），看了栈的应用之一，做算术表达式解析计算，但那个例子中没有把括号的逻辑加进去，苦想一段时间后还是没有结果，于是Google出一些表达式解析的方案，觉得用后缀表达式解析是最方便的，遂用Ruby实现了一个，支持由数字、加减乘除和括号组成的表达式，因为主要目的是对栈的应用，所以一些地方能简则简。

class MyParser
  PRECEDENCE = [
    ['(', ')'],
    ['|'],
    ['&'],
    ['+', '-'],
    ['*', '/']
  ]
  
  REG_VARIABLE = /\d+(?:\.\d+)?/
  REG_OPERATOR = /[\+\-\*\/\|\&]/
  REG_PARENTHESIS = /[\(\)]/
  REG_SPACE = /\s+/
  
  def self.exec(exp)
    exec_postfix parse_to_postfix(exp)
  end
  
  # 将表达式解析成后缀表达式，这里后缀表达式改用数组
  def self.parse_to_postfix(exp)
    postfix_exp, stack = [], []
    # 每次从exp中取出第一段标志符（数字，操作符，括号），进行分析，exp中的标志符取完后退出循环
    until exp.nil? or exp.size == 0
      case exp
      when /^(#{REG_VARIABLE})/ # 数字
        token = $1
        postfix_exp << token
      when /^(#{REG_OPERATOR})/ # 操作符
        token = $1
        # 这个if和else可以合在一起的，但我觉得这样逻辑更清晰，脑袋笨了冒得法啊
        if stack.empty?
          stack << token
        else
          # 原来这里的逻辑错了，现已改正
          # 当读取的操作符优先级不高于栈中的操作符优先级时，需要依次将栈中的操作符弹出送到表达式中
          while stack.size > 0 && precedence(token) <= precedence(stack.last)
            postfix_exp << stack.pop
          end
          stack << token
        end
      when /^(#{REG_PARENTHESIS})/ # 括号
        token = $1
        case token
        when '('
          stack << token
        when ')'
          postfix_exp << stack.pop while !stack.empty? && stack.last != '('
          # 因为一般')'都会有匹配的'('，正常情况下这里stack的最后一个元素一定是'('
          raise "mismatched parenthesis '#{token}'" if stack.last != '('
          stack.pop
        else
          raise "parenthesis '#{token}' wrong"
        end
      when /^(#{REG_SPACE})/ # 空格，这个只是额外处理，和表达式转换的核心逻辑无关
        token = $1
      else
        raise "unknown token! expression is '#{exp}'"
      end
      exp = exp[token.size..-1]
    end

    until stack.empty?
      # 检查括号是否匹配的，因为stack中只会压入'('，不会压入')'
      # 如果表达式括号匹配的话，到这里stack中所有的'('应该都已经被处理了
      raise "mismatched parenthesis '('" if stack.last == '('
      postfix_exp << stack.pop
    end
    postfix_exp
  end
  
  # 根据后缀表达式计算结果
  def self.exec_postfix(postfix_exp)
    stack = []
    postfix_exp.each do |token|
      case token
      when REG_VARIABLE # 变量直接压入stack
        stack << token.to_f
      when REG_OPERATOR # 碰到操作符，从stack中弹出两个数，进行计算，再将结果压入
        raise 'stack size < 2'if stack.size < 2
        d2, d1 = stack.pop, stack.pop
        stack << exec_exp(d1, token, d2)
      end
    end
    raise 'final stack size must be 1' if stack.size != 1
    stack.first
  end
  
  # 计算操作符的优先级，返回一个数字，数字越大优先级越高
  def self.precedence(op)
    re = PRECEDENCE.index { |group| group.include?(op) }
    raise "unknown operator '#{op}'" if re.nil?
    re
  end
  
  # 输入两个数和二元运算符，进行计算，返回结果
  # 例：exec_exp(1, '+', 2)  =>  3
  def self.exec_exp(d1, op, d2)
    case op
    when REG_OPERATOR
      d1.send(op, d2)
    else
      raise "operator '#{op}' wrong"
    end
  end
end

# 测试一下，看算的对不对
puts 'TEST CALCULATE'
[
  ['1+2*3', 7.0], # 前面是表达式，后面是期望的计算结果，下同
  ['1*2-3', -1.0],
  ['10-(4-2)*3', 4.0],
  ['2*(24-(3*10))+11', -1.0]
].each do |exp, result|
  puts exp
  postfix_exp = MyParser.parse_to_postfix(exp)
  puts "  #{'parse'.ljust(9)} = #{postfix_exp}"
  puts "  #{'calc'.ljust(9)} = #{MyParser.exec_postfix postfix_exp}"
  puts "  #{'expect'.ljust(9)} = #{result}"
end

# 测试后缀表达式是否正确
puts 'TEST POSTFIX EXPRESSION'
[
  ['1|2&3+4|5', '1234+&|5|'],
  ['1-2|3*4&5', '12-34*5&|'],
  ['(1|2)&3+(4|5)', '12|345|+&']
].each do |exp, result|
  puts exp
  postfix_exp = MyParser.parse_to_postfix(exp).join
  puts "  #{'parse'.ljust(9)} = #{postfix_exp}"
  puts "  #{'expect'.ljust(9)} = #{result}"
end

运行 结果如下：

1+2*3
  parse     = ["1", "2", "3", "*", "+"]
  calc      = 7.0
  expect    = 7.0
1*2-3
  parse     = ["1", "2", "*", "3", "-"]
  calc      = -1.0
  expect    = -1.0
10-(4-2)*3
  parse     = ["10", "4", "2", "-", "3", "*", "-"]
  calc      = 4.0
  expect    = 4.0
2*(24-(3*10))+11
  parse     = ["2", "24", "3", "10", "*", "-", "*", "11", "+"]
  calc      = -1.0
  expect    = -1.0

 嗯，至少没算错……

下面说说大概思路：

基本逻辑就是两步，先把输入的表达式（我们一般的表达式写法都是中缀表达式）转换成后缀表达式，然后用后缀表达式进行计算。比如这样：

# 中缀表达式，我们通常写的形式
1*2+3
# 这是后缀表达式的写法，基本上是把运算符放到数字后面，
# 读法为从前往后读，碰到运算符，就把运算符前的两个数字代入计算，计算结果就取代了原来的两个数字和运算符，以此类推
12*3+
# 再看个复杂点的，中缀表达式如下
1+2*3
# 后缀表达式，
123*+
# 这个是有括号的中缀表达式
(1+2)*3
# 换成后缀表达式就是这样，可以看出，后缀表达式是没有括号和运算符优先级的，比较方便由计算机处理
这正是要转换成后缀表达式的原因
12+3*

后缀表达式很容易被计算机处理，逻辑也不复杂。

其实数据结构教程里的示例代码的原理和上面的Ruby代码十分类似，只是一个直接计算，一个是转换成后缀表达式。

个人感觉数据结构的示例，把对栈的操作和数据计算混在一起，比较乱。而且要处理括号的逻辑，可能要采用递归才能实现，比较麻烦。

 

参考资料

 

这篇文章是思路来源，我用Ruby重新实现了一把，补充一些细节，里面讲表达式转换逻辑和后缀表达式计算逻辑比较详细

利用堆栈解析算术表达式

这篇是我原来比较倾向的思路，完全采用递归，将表达式不停拆分解析，直到最基本的元素，可惜代码太长，比较复杂,懒得看了

解析表达式--Java编程艺术

这是RednaxelaFX 童鞋补充的资料，Wikipedia上表达式转换的文章，感叹一句：砖业人士啊

Shunting-yard algorithm

评论

8 楼 yourfei 2010-02-02  

我大学的时候做编译原理课程设计就是做的这个，当时还得了个优！
当时是用C++做的，MFC做的界面，输出有逆波兰式、三元式、四元式、树形结构和计算结果。树形结构式用MFC的Tree控件做的。现在想想当时挑灯夜战写的代码就感慨万千！

7 楼 linliangyi2007 2010-01-31  

楼主有兴趣可以参考这个东东
http://linliangyi2007.iteye.com/blog/337069
一起讨论啊

6 楼 darkbaby123 2010-01-28  

都改正了，这样确实严谨些，原来偷懒都没判断括号匹配的。

5 楼 RednaxelaFX 2010-01-26  

darkbaby123 写道

RednaxelaFX 写道

good，楼主一下就发现问题所在了 ^_^
还有些小地方可能要注意的，例如让顶楼的程序去执行表达式")"的话……跟核心算法没直接关系，只是边界条件要检查一下而已。
另外就是想提一下这个解析算法叫作shunting-yard algorithm，以后查资料的话用这个关键字会比较容易找到。

嗯，受教了。不过你说的“边界条件检查”该如何实现呢？不是很明白怎么把括号和算法逻辑分开。

参考Wikipedia上给出的算法描述吧。注意这段：

引用

If the token is a right parenthesis:
- Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
- Pop the left parenthesis from the stack, but not onto the output queue.
- If the token at the top of the stack is a function token, pop it onto the output queue.
- If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

对应到顶楼的代码，至少应该做这样的修改：
parse_to_postfix的循环中

when /^(#{REG_PARENTHESIS})/ # 括号
  token = $1
  case token
  when '('
    stack << token
  when ')'
    postfix_exp << stack.pop while !stack.empty? && stack.last != '('
    raise "mismatched parenthesis '#{token}'" if stack.last != '('
    stack.pop
  end

循环结束后临返回前的那组pop：

until stack.empty?
  raise "mismatched parenthesis '('" if stack.last == '('
  postfix_exp << stack.pop
end

这样括号不匹配的问题就会减轻些……

4 楼 darkbaby123 2010-01-26  

RednaxelaFX 写道

good，楼主一下就发现问题所在了 ^_^
还有些小地方可能要注意的，例如让顶楼的程序去执行表达式")"的话……跟核心算法没直接关系，只是边界条件要检查一下而已。
另外就是想提一下这个解析算法叫作shunting-yard algorithm，以后查资料的话用这个关键字会比较容易找到。

嗯，受教了。不过你说的“边界条件检查”该如何实现呢？不是很明白怎么把括号和算法逻辑分开。

3 楼 RednaxelaFX 2010-01-26  

good，楼主一下就发现问题所在了 ^_^
还有些小地方可能要注意的，例如让顶楼的程序去执行表达式")"的话……跟核心算法没直接关系，只是边界条件要检查一下而已。
另外就是想提一下这个解析算法叫作shunting-yard algorithm，以后查资料的话用这个关键字会比较容易找到。

2 楼 darkbaby123 2010-01-26  

后缀表达式的解析确实有问题，原来居然没注意到
主要是对操作符的判断这一块，应该改成循环判断的

when /^(#{REG_OPERATOR})/ # 操作符
        token = $1
        if stack.empty?
          stack << token
        else
          while stack.size > 0 && precedence(token) <= precedence(stack.last)
            postfix_exp << stack.pop
          end
          stack << token
        end

BTW：优先级的英文错误也改了，英语实在不好……以后要努力了

1 楼 RednaxelaFX 2010-01-26  

well...因为楼主参考的文章就的算法就有瑕疵，所以楼主搬过来的时候也有一样的问题。
顶楼的文章要解析的表达式只有2个有效优先级（顺带，运算符优先级是用precedence表示的），加减是一个，乘除是一个，括号因为在解析的时候被特别处理所以不算。在这个条件下，某部分代码是没问题的。但如果有效优先级增加到2个以上，例如说

class MyParser
  PRIORITY = [
    ['(', ')'],
    ['|'],
    ['&'],
    ['+', '-'],
    ['*', '/']
  ]

# ...
end

其中&与|分别表示按位与和按位或，前者优先级比后者高，两者都比加法优先级低。那么顶楼代码中某个入栈/出栈操作就会出问题了。楼主自己试试去发现这个问题吧？

举例：表达式

1 | 2 & 3 + 4 | 5

应该转换为这样的后缀表达式：

['1', '2', '3', '4', '+', '&', '|', '5', '|']

而顶楼的代码照现在的逻辑会将其变为：

['1', '2', '3', '4', '+', '5', '|', '&', '|']

（这个表达式照现在顶楼代码的写法求不了值这是另外一回事了，跟解析方式没关系）