论坛首页 编程语言技术论坛

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

浏览 7778 次
精华帖 (0) :: 良好帖 (7) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2010-01-24   最后修改:2010-02-08

最近补习数据结构(谁叫我不是科班出身呢),看了栈的应用之一,做算术表达式解析计算,但那个例子中没有把括号的逻辑加进去,苦想一段时间后还是没有结果,于是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

   发表时间:2010-01-26   最后修改: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', '|', '&', '|']

(这个表达式照现在顶楼代码的写法求不了值这是另外一回事了,跟解析方式没关系)
0 请登录后投票
   发表时间: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:优先级的英文错误也改了,英语实在不好……以后要努力了
0 请登录后投票
   发表时间:2010-01-26   最后修改:2010-01-26
good,楼主一下就发现问题所在了 ^_^
还有些小地方可能要注意的,例如让顶楼的程序去执行表达式")"的话……跟核心算法没直接关系,只是边界条件要检查一下而已。
另外就是想提一下这个解析算法叫作shunting-yard algorithm,以后查资料的话用这个关键字会比较容易找到。
0 请登录后投票
   发表时间:2010-01-26  
RednaxelaFX 写道
good,楼主一下就发现问题所在了 ^_^
还有些小地方可能要注意的,例如让顶楼的程序去执行表达式")"的话……跟核心算法没直接关系,只是边界条件要检查一下而已。
另外就是想提一下这个解析算法叫作shunting-yard algorithm,以后查资料的话用这个关键字会比较容易找到。

嗯,受教了。不过你说的“边界条件检查”该如何实现呢?不是很明白怎么把括号和算法逻辑分开。
0 请登录后投票
   发表时间: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

这样括号不匹配的问题就会减轻些……
0 请登录后投票
   发表时间:2010-01-28  
都改正了,这样确实严谨些,原来偷懒都没判断括号匹配的。
0 请登录后投票
   发表时间:2010-01-31  
楼主有兴趣可以参考这个东东
http://linliangyi2007.iteye.com/blog/337069
一起讨论啊
0 请登录后投票
   发表时间:2010-02-02  
我大学的时候做编译原理课程设计就是做的这个,当时还得了个优!
当时是用C++做的,MFC做的界面,输出有逆波兰式、三元式、四元式、树形结构和计算结果。树形结构式用MFC的Tree控件做的。现在想想当时挑灯夜战写的代码就感慨万千!
0 请登录后投票
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics