文档章节

Clojure: 实现简单的数学表达式计算

陈亦
 陈亦
发布于 2016/03/17 16:00
字数 1993
阅读 384
收藏 0

我之前在知乎上回答了问题 按照运算符优先数法,画出算术表达式求值时,操作数栈和运算符栈的变化过程 。这次一方面也算是温故而知新,另一方面借此领略Clojure函数式编程之美。为了节省篇幅,本文只考虑 +、-、*、/ 这几种基本运算符以及只考虑小于10的整数运算。

栈变化图示

我们人类使用的算术表达式是中缀表达式,而计算机采用后缀表达式,也即逆波兰式。第一种方式是将表达式转为后缀表达式,再进行求值;第二种方式是直接对中缀表达式进行求值。本文就直接采用第二种方式了。

比如要对表达式 9-2*4+9/3 进行求值。首先需要使用2个栈来分别保存运算数和运算符,分别记为 opnd 和 optr。对表达式逐家符读入:

1、读入字符 '9',因为是运算数,则放入 opnd 栈中,剩余待读入字符串为:-2*4+9/3,此时 opnd 栈和 optr 栈如下图所示:


2、读入字符 '-',发现是运算符,则先和 optr 栈顶作比较,因为 optr 栈是空栈,故直接入栈 optr。剩余待读入字符串为:2*4+9/3,此时 opnd 栈和 optr 栈如下图所示:


3、接下来读入字符'2',发现是运算数,则入栈 opnd,剩余待读入字符串为:*4+9/3,此时opnd 栈和 optr 栈如下图所示:


4、接下来读入字符 '*',发现是运算符,则跟 optr 栈顶字符 '-' 进行比较,'*' 优先级高于 '-',因此直接将 '*' 入栈 optr,剩余待读入字符串为:4+9/3,此时 opnd 栈和 optr 栈如下图所示:


5、接下来读入字符 '4',因为是运算数,则直接入栈 opnd,剩余待读入字符串为:+9/3,此时 opnd 栈和 optr 栈如下图所示:


6、接下来读入字符 '+',发现是运算符,则跟 optr 栈顶元素 '*' 进行比较,发现 '+' 的优先级小于 '*',则将 optr 出栈,得到运算符 '*',将 opnd 出2次栈,得到字符 '4' 和 '2',令 '4' 和 '2' 分别作为运算符 '*' 的左右操作数(即 4 * 2)得到结果为 '8',将 '8' 入栈 opnd。剩余待读入字符为:9/3,此时 opnd 栈和 optr 栈如下图所示:


7、此时 '+' 运算符还未入栈 optr,继续与 optr 栈顶元素 '-' 进行比较,'+' 优先级不小于 '-',则出栈 optr 得到运算符 '-',将 opnd 出2次栈,得到字符 '9' 和 '8',令 '9' 和 '8' 分别作为运算符 '-' 的左右操作数(即 9 - 8)得到结果为 '1',将 '1' 入栈 opnd,此时 optr 栈为空,将 '+' 运算符入栈 optr,剩余待读入字符为:9/3,此时 opnd 栈和 optr 栈如下图所示:


8、读入字符 '9',入栈 opnd,剩余待读入字符串为:/3,此时 opnd 栈和 optr 栈如下图所示:

9、读入字符 '/',发现是运算符,跟 optr 栈顶 '+' 进行比较,因为 '/' 的优先级高于 '+',则直接将 '/' 入栈 optr,剩余待读入字符串为:3,此时 opnd 栈和 optr 栈如下图所示;


10、读入字符 '3',入栈 opnd,此时表达式已全部读取完成,此时 opnd 栈和 optr 栈如下图所示:


11、optr 栈不为空,则出栈得到运算符 '/',从 opnd 出栈2次,得到 '9' 和 '3' 分别作为左右操作数进行运算(即9/3),得到结果为 '3',并入栈 opnd。此时 opnd 栈和 optr 栈如下图所示:


12、optr 栈不为空,则出栈 optr,得到运算符 '+',从 opnd 出栈2次,得到 '1' 和 '3' 分别作为运算符 '+' 的左右操作数进行运算(即1+3),得到结果 '4'并入栈 opnd,此时 opnd 栈和 optr 栈如下图所示:


13、此时 optr 栈已为空,则将 opnd 出栈,得到 '4',即为表达式 9-2*4+9/3 的求值结果。

原理

1、首先需准备2个栈结构,分别用于保存操作数和运算符;

2、需对运算符的优先级进行划分;

3、表达式从左到右逐字符读入;

4、操作数直接入栈;

5、运算符入栈前需先进行判定:如果运算符栈为空,则直接入栈。否则取出栈顶,进行优先级比较,如果待读入运算符比栈顶运算符优先级高,则直接入栈待读入运算符。否则须先出栈,进行运算完后方入栈待读入运算符;

6、当执行计算时,从操作数栈中连续出栈2次,先出栈的为右操作数,后出栈的为左操作数;

7、当表达式全部读取完成,则以运算符栈是否为空为依据,依次出栈对操作数进行计算,计算的结果再次入栈操作数栈;

8、当运算符栈为空时,出栈操作数栈,即为此次表达式的计算结果。

实现

本文限于篇幅,只考虑的运算符为:+、-、*、/,操作数为小于10的整。所以无须处理复杂的运算符优先级关系,并且在读入表达式时,只须对单个字符判断为操作数或运算符。

一、为什么是Clojure

clojure是基于JVM的函数式编程语言,它借签了Haskell、Lisp等函数式语言的优点,并形成自己的独有风格。它也是一门动态语言:变量不可变,atom、ref、promise、future、delay使它天生适用于多核高并发开发任务。完备的宏定义、数据协议和类型、多重方法等赋予这门语言无限的可能。极尽JVM之所能,易于和java的互操作性,立于JVM的强大生态之上,又还有什么理由不选择Clojure呢?

二、安装Clojure

Clojure是基于JVM的语言,所以你应该已经安装好JVM环境了。

wget https://raw.githubusercontent.com/technomancy/leiningen/stable/bin/lein
mv lein ~/bin/
chmod a+x ~/bin/lein

lein脚本已经处于你的PATH之中,如若不然,请在 ~/.profile 里添加:

export PATH=~/.profile:$PATH

然后执行:

source ~/.profile

第一次执行 lein 会进行自我安装,安装完毕即可通过 lein repl 进入交互式开发环境。

我们通过 lein new 来创建项目:

lein new calc

三、代码实现

栈直接用java提供的 java.util.Stack 类,源代码在 src/calc/core.clj 中,如下:

(ns calc.core
  (:import [java.util Stack]))

; 运算符及优先级定义
(def ^:private op_map {\+ 5, \- 5, \* 6, \/ 6})

(defn isdigit? [c] (#{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} c))

(defn -main [& args]
  (let [_expr (seq (nth args 0))]
    (loop [expr _expr opnd (Stack.) optr (Stack.)]
      (if (empty? expr)
        (do
          ;(println opnd optr)
          (loop [not_ept (not (empty? optr))]
            (if (not not_ept) (println (str "计算结果为:" (.. opnd (pop))))
              (do
                (let [op_c (.. optr (pop)) rn (.. opnd (pop)) ln (.. opnd (pop))
                      v (case op_c
                          \+ (+ ln rn)
                          \- (- ln rn)
                          \* (* ln rn)
                          \/ (/ ln rn))]
                  ;(println op_c ln rn v opnd optr)
                  (.. opnd (push v))
                  (recur (not (empty? optr))))))))
        (let [[c & _rest] expr] (if (isdigit? c) (.. opnd (push (Integer. (str c))))
                                  (if (empty? optr) (.. optr (push c))
                                                        (loop [not_ept (not (empty? optr))]
                                                          (if (not not_ept)
                                                            (.. optr (push c))
                                                            (let [op_c (.. optr (peek))]
                                                              (if (> (op_map c) (op_map op_c)) (.. optr (push c))
                                                                (do
                                                                  (.. optr (pop))
                                                                  (let [rn (.. opnd (pop)) ln (.. opnd (pop))
                                                                        v (case op_c
                                                                            \+ (+ ln rn)
                                                                            \- (- ln rn)
                                                                            \* (* ln rn)
                                                                            \/ (/ ln rn))]
                                                                    (.. opnd (push v))
                                                                    ;(println ln rn v opnd optr)
                                                                    (recur (not (empty? optr)))))
                                                                ))))))
          (recur _rest opnd optr))))))

在 project.clj 中配置入口,增加一行:

:main calc.core/-main

在命令行中执行:

$ lein run 9-2*4+9/3
计算结果为:4

此程序只是为了演示,并不通用。写惯了命令式程序,很容易被函数式语言弄得晕头转向。欲练神功,先自废武功~

另:感谢 敏敏郡主 ^_^






© 著作权归作者所有

陈亦
粉丝 241
博文 23
码字总数 53194
作品 0
浦东
高级程序员
私信 提问
clojure 新手指南(3)复杂表达式求值

为了理解复杂的表达式和对它的操作,一个首要的前提就是理解”前缀表达式“。这可能会花费你一点时间来习惯它。不过我相信你会很快的爱上这种规则的。你想想,如果你要对多个值进行同一种运算...

凯奥斯
2013/07/03
726
1
用 Java 编写的 miniKanren 实现--Java8kanren

Java8kanren 是用 Java 编写的 miniKanren 实现。 miniKanren 是一类关系型编程语言。miniKanren 可以通过给定的关系表达式和计算结果来反向推导,找出符合条件的输入变量的取值组合。程序员...

匿名
2016/12/26
314
0
JVM上的并发编程利器:Clojure语言

诞生于2007年的Clojure是JVM平台上的Lisp实现,Lisp 以强大的功能和表达性而著称,但应用范围存在着固定的局限,于是发起人Rich Hickey设计Clojure的初衷便是希望得到一门能够服务于高并发应...

红薯
2010/09/06
1K
2
给 JavaScript 开发者讲讲函数式编程

和大多数人一样,我在几个月前听到了很多关于函数式编程的东西,不过并没有更深入的了解。于我而言,可能只是一个流行词罢了。从那时起,我开始更深地了解函数式编程并且我觉得应该为那些总能...

oschina
2016/04/30
6.4K
9
史上最全的机器学习资料(上)

摘要: 机器学习牵涉的编程语言十分之广,包括了MATLAB、Python、Clojure、Ruby等等。为了让开发者更加广泛、深入地了解机器学习,云栖社区组织翻译了GitHub Awesome Machine Learning 资源,...

NathanJoy
2016/08/30
723
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
49分钟前
15
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
8
0
太全了|万字详解Docker架构原理、功能及使用

一、简介 1、了解Docker的前生LXC LXC为Linux Container的简写。可以提供轻量级的虚拟化,以便隔离进程和资源,而且不需要提供指令解释机制以及全虚拟化的其他复杂性。相当于C++中的NameSpa...

Java技术剑
今天
21
0
Wifiphisher —— 非常非常非常流氓的 WIFI 网络钓鱼框架

编者注:这是一个非常流氓的 WIFI 网络钓鱼工具,甚至可能是非法的工具(取决于你的使用场景)。在没有事先获得许可的情况下使用 Wifiphisher 攻击基础网络设施将被视为非法活动。使用时请遵...

红薯
今天
82
1
MongoDB 4 on CentOS 7安装指南

本教程为CentOS x86_64 7.x操作系统下,MongoDB Community x86_64 4.2(GA)安装指南。 安装方式一:yum repo在线安装 [此方式较为简单,官方推荐] Step1:新建MongDB社区版Yum镜像源。 # vim ...

王焱君
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部