Haskell Haskell 逆波兰计算例子

chenge · 2013年05月08日 · 最后由 zputee 回复于 2013年05月09日 · 9979 次阅读

确实简洁,不妨想一下 Ruby 怎么写?来自《Haskell 趣学指南》。

import Data.List   

solveRPN = head . foldl foldingFunction [] . words   
    where   foldingFunction (x:y:ys) "*" = (x * y):ys   
            foldingFunction (x:y:ys) "+" = (x + y):ys   
            foldingFunction (x:y:ys) "-" = (y - x):ys   
            foldingFunction xs numberString = read numberString:xs

--solveRPN "10 4 3 +" 

solveRPN 和 foldingFunction 的类型最好标注一下,还有 foldingFunction 这个名字不够有意义

haskell 本身写递归就非常合适 所以当然短啦 而且很巧。。 前两天刚写了这个: https://github.com/tony612/reverse-polish-notation-transition/blob/master/postfix.rb

除了计算出结果,还有转化为 postfix 和 infix 的

(PS:不过话说,这个 “10 4 3 +” 好像不是合法的逆波兰式吧。。)

#2 楼 @Tony612 例子没有递归

def solveRPN rpnexp
  rpnexp.split.inject [] do |stack, cur|
    foldingFunction stack, cur
  end.first
end

def foldingFunction stack, cur
  case cur
  when '*'
    stack << stack.pop.to_i * stack.pop.to_i
  when '+'
    stack << stack.pop.to_i + stack.pop.to_i
  when '-'
    stack << 0 - stack.pop.to_i + stack.pop.to_i
  else
    stack << cur
  end
end

puts solveRPN "10 4 3 + 2 * -"

照着这个 Haskell 的版本写了一个,当年看这本 learn you a haskell 就是这章 Functional Solving Problems 特别有启发,推荐读读这一章!

不知道算浮点类型的结果准不准

The ruby way...

def solve_rpn expr
  expr.scan(%r"(\d+)|([+\-*/])").inject [] do |stack, (num, op)|
    stack << (num ? num.to_i : stack.pop(2).reverse.inject(op))
  end.last
end
solve_rpn "10 4 3 + 2 * -"

#7 楼 @luikore 这正则用的太漂亮了。。 还有 原来 inject 还可以传参数的 大神你又要引起无数膜拜了 😆

#7 楼 @luikore 效果不错。加上浮点数方便么?

#7 楼 @luikore bug: solve_rpn "5 -4 -"

#9 楼 @chenge 改改正则就可以 (%r"(-?\d+(?:\.\d+(?:[eE]\d+)?)?)|([+\-*/])"), 另一个方法是用 scanf

require 'scanf'
def solve_rpn expr
  expr.split.inject [] do |stack, x|
    stack << (x.scanf('%f').first or stack.pop(2).reverse.inject(x))
  end.last
end
solve_rpn "10 4.1 3.0e1 + -2 * -"

#10 楼 @quakewang 嗯嗯... 还是应该 split...

#9 楼 @chenge

def solveRPN rpnexp
 rpnexp.split.inject [] do |stack, c|
  stack<<("+-*\\".include?(c)? stack.pop(2).reverse.map(&:to_f).inject(c) : c)
 end.first
end
solveRPN "10 4.1 3.0e1 + -2 * -"
require "scanf"
def solveRPN1 exp
  stk=[];
  exp.split.each{|c|stk<<(c.scanf('%f').first||stk.pop(2).reverse.inject(c))}
  stk.first
end
solveRPN1 "10 4.1 3.0e1 + -2 * -"
需要 登录 后方可回复, 如果你还没有账号请 注册新账号