什么是表达式&＃xff1f;
计算机如何表达和计算一个算术表达式&＃xff1f;
搞懂了这个问题&＃xff0c;我们也就弄清楚了如何去解析一个算术表达式。甚至再多学一点&＃xff0c;就可以写一个可以进行简单编程的计算器。
一个表达式就是一个顺序表list&＃xff0c;是一个由操作数(Operand, 算数)和操作符(Operator, 算符)按某种顺序组合起来的序列。
表示一个算术表达式的方法通常有三种&＃xff0c;前缀表达式&＃xff0c;也称为波兰表达式、中缀表达式&＃xff0c;也就是我们人类常用的这种&＃xff0c;后缀表达式&＃xff0c;也称为逆波兰表达式。前缀表达式&＃xff0c;顾名思义&＃xff0c;就是操作符置于其对应的操作数的前面的表达式&＃xff0c;而后缀表达式则是操作符置于对应的操作数之后的表达式&＃xff0c;中缀则不用说&＃xff0c;学过小学数学的人都知道。
解析表达式&＃xff0c;就是要将它的的各项和各个运算符逐个读入内存&＃xff0c;然后构造某种数据结构(通常是表达式树)将它们关联和表达出来。
表达式树的特点是&＃xff1a;叶节点上存放操作数&＃xff0c;而内部节点存放操作符&＃xff0c;一个操作符的子树是它的一个子表达式(求值之后便是它的操作数)。构建好表达式树之后&＃xff0c;通过不同的遍历算法即可生成不同的表达式。对表达式树执行前序遍历&＃xff0c;生成的是前缀表达式(操作符置于操作数之前)&＃xff1b;对表达式树执行中序遍历&＃xff0c;生成的是中缀表达式&＃xff1b;对表达式树执行后序遍历&＃xff0c;生成的是后缀表达式&＃xff1b;
下面是一些表达式树![]()
![]()
![]()
和对应的中缀表达式
1 &＃43; 2
2 * (3 &＃43; (3 &＃43; 1))
(((1 / 2) * 3) - 4) &＃43; 5
等价的前缀表达式
&＃43; 1 2
* 2 &＃43; 3 &＃43; 3 1
&＃43; - * / 1 2 3 4 5
以及等价的后缀表达式
1 2 &＃43;
2 3 3 1 &＃43; &＃43; *
1 2 / 3 * 4 - 5 &＃43;
看上去前缀表达式和后缀表达式比较复杂&＃xff0c;而中缀表达式则较为简单。但事实上&＃xff0c;对前缀和后缀两种表达式的求值比对中缀表达式的求值简单得多。这是因为前置和后置的操作符保证了操作符与操作数结合的唯一性。总之&＃xff0c;前缀表达式和后缀表达式是没有歧义的表达式&＃xff0c;而中缀表达式则是一种有歧义的表达式&＃xff0c;所以需要借助括号和算符结合的优先级来消除歧义。正所谓抓住了树根&＃xff0c;你就抓住了一切&＃xff1b;
抓住了叶子&＃xff0c;你就得一片叶子。
在现代计算机中&＃xff0c;中缀表达式通常用于编写人类可读的源代码&＃xff0c;例如大多数的编程语言的表达式都是中缀表达式。不过&＃xff0c;也有使用前缀表达式进行编程的语言&＃xff0c;比如汇编语言。为什么是是这样呢&＃xff1f;因为前缀表达式就像是一条条的命令&＃xff0c;这样的命令适合机器一步步的执行&＃xff0c;而中缀表达式更适合人类的书写和阅读习惯。
表达式的求值
求值(evaluate)&＃xff0c;是常见于编译原理和编程语言相关领域的一个术语&＃xff0c;表示计算并返回一个表达式或一段程序的结果。
如果已经有了该表达式的表达式树&＃xff0c;我们可以直接对表达式树进行求值。由于树本身的自相似结构&＃xff0c;以及树的遍历通常要用到递归或栈&＃xff0c;使用递归函数对表达式树进行求值是最简单的方式。该递归函数的特点是对每一个节点&＃xff0c;判断它是操作数还是操作符。如果是操作数&＃xff0c;直接返回&＃xff1b;如果是操作符&＃xff0c;那么就递归地计算它的各个子项(操作数)&＃xff0c;再用该操作符把各个操作数计算出来并返回。
当然&＃xff0c;直接使用一个栈对表达式进行求值亦可&＃xff0c;就像借助栈来对树进行非递归的遍历一样。下面讲述如何对前缀、中缀和后缀三种的四则运算表达式进行求值。在之后的表达式树的生成一节中&＃xff0c;将会讲解如何解析一个表达式生成它的表达式树。
前缀和后缀表达式的求值算法比较简单&＃xff0c;中缀则较为困难。首先来看下后缀表达式的求值过程&＃xff0c;
;;; 判断 elem 是否在 elems 中
(define(in elem elems)
(if(atom? elems)
(eqv?elems elem)
(if(null?elems)
#f
(or(in elem (carelems))
(in elem (cdrelems))))))
(defineeval-suffix
(lambda(expr)
(defineoperator? (lambda(elem) (in elem &＃39;(&＃43; - * /))))
(letloop ([expr expr][stack &＃39;()])
(if(null?expr)
(carstack)
(let([elem (carexpr)]
[expr (cdrexpr)])
(if(operator? elem)
(let([op (evalelem)]
[first-operand (cadrstack)]
[second-operand (carstack)]
[stack (cddrstack)])
(loop expr (cons(op first-operand second-operand) stack)))
(loop expr (conselem stack))))))))
(printf "~a\n" (eval-suffix &＃39;(1 2 &＃43;))) ; 3
(printf "~a\n" (eval-suffix &＃39;(2 3 3 1 &＃43; &＃43; *))) ; 14
(printf "~a\n" (eval-suffix &＃39;(1 2 / 3 * 4 - 5 &＃43;))) ; 5/2
看起来很简单&＃xff0c;总结为一条规则就是&＃xff1a;从左往右顺序遍历每个操作数和操作符&＃xff0c;遇见操作数压栈&＃xff0c;遇到操作符弾栈执行对应计算&＃xff0c;并将结果压入栈中。最后&＃xff0c;返回栈顶的值。
前缀表达式的求值算法与此类似&＃xff0c;只不过遍历操作符和操作数的时候要从右往左地进行&＃xff0c;从栈中取操作数的顺序也与后缀表达式的相反。因此&＃xff0c;将对后缀表达式进行求值的函数稍微改一下&＃xff0c;就可以用来对前缀表达式进行求值了。
;;; 判断 elem 是否在 elems 中
(define(in elem elems)
(if(atom? elems)
(eqv?elems elem)
(if(null?elems)
#f
(or(in elem (carelems))
(in elem (cdrelems))))))
(defineoperator? (lambda(elem) (in elem &＃39;(&＃43; - * /))))
(define(gen-eval get-first-operand get-second-operand)
(lambda(expr)
(letloop ([expr expr][stack &＃39;()])
(if(null?expr)
(carstack)
(let([elem (carexpr)]
[expr (cdrexpr)])
(if(operator? elem)
(let([op (evalelem)]
[first-operand (get-first-operand stack)]
[second-operand (get-second-operand stack)]
[stack (cddrstack)])
(loop expr (cons(op first-operand second-operand) stack)))
(loop expr (conselem stack))))))))
(defineeval-suffix (gen-eval cadr car))
(defineeval-prefix (lambda(expr) ((gen-eval car cadr) (reverseexpr))))![]()
写到这里&＃xff0c;放张图片&＃xff0c;向用SublimeText的同学推荐一下我为SublimeText开发的括号高亮插件&＃xff1a;RainbowBrackets&＃xff0c;和Scheme语言的语法高亮、代码补全插件SublimeScheme. 功能不尽完善&＃xff0c;还望同学多多提意见。
中缀表达式的求值
(defineeval-infix
(lambda(expr)
(defineeval-help
(lambda(handled-value next-expr)
(if(null?next-expr)
handled-value
(let([op (carnext-expr)])
(caseop
[(&＃43;-) (eval(listop handled-value (eval-infix (cdrnext-expr))))]
[(*/) (eval-help (eval(listop handled-value (eval-infix (cadrnext-expr))))
(cddrnext-expr))])))))
(if(atom? expr)
(evalexpr)
(eval-help (eval-infix (carexpr)) (cdrexpr)))))
在中缀表达式的求值过程中&＃xff0c;基于处理算符优先级和对自相似性的考虑&＃xff0c;用到了递归函数。
S表达式
讲完了前缀中缀后缀三种表达式&＃xff0c;下面&＃xff0c;我们来讲一种更简单也更通用的表达式&＃xff0c;它叫S表达式。
其实S表达式也是一种前缀表达式&＃xff0c;只不过&＃xff0c;它的每一个表达式都被用括弧括起来&＃xff0c;而这括弧巧妙地隔离了优先级、参数个数(它的参数个数不限)等表达式自带的刺&＃xff0c;并提供了自相似性&＃xff0c;甚至提供了作用域&＃xff0c;使得尽管S表达式可以异常复杂&＃xff0c;但对S表达式的求值却极其简单。而它的操作符也因此可以更平凡因而更有表达力&＃xff0c;既可以是各种简单的算符&＃xff0c;也可以是一个复杂的函数。它的操作数可以是一个简单的原子类型(数值或符号)&＃xff0c;也可以是另一个嵌套的表达式。通过层层嵌套&＃xff0c;使得s表达式本身就具有一种强有力的表示数据的能力。可以说&＃xff0c;一个S表达式就是一个表达式树数据结构的字符化表示。
下面是一个简单的S表达式
(&＃43;1 (*2 (/3 4)))
它也是lisp编程语言和它的各种方言的一个程序片段。
lisp是一门强大的函数式编程语言&＃xff0c;但相较于C&＃xff0c;C&＃43;&＃43;&＃xff0c;Javascript&＃xff0c;Python等语言&＃xff0c;lisp语言并不怎么流行。这种处境在很大程度上是由充斥于lisp程序里的层层嵌套的括号导致的。对大部分人来说&＃xff0c;层层嵌套看上去很怪异&＃xff0c;就像某种魔咒&＃xff0c;令他们害怕而悄悄远离。我想&＃xff0c;这跟一个在别人看来比较怪异的同学在班上的待遇没有区别。确实&＃xff0c;
![]()
要比
![]()
简洁不少。可以说&＃xff0c;lisp的括号是屏障&＃xff0c;也是墙壁&＃xff0c;屏蔽掉了污染&＃xff0c;也挡住了很多人。
关于另外一些原因&＃xff0c;我会说&＃xff0c;我个人觉得成员运算符『.』和下标运算符『[]』是两个很重要的操作符&＃xff0c;它们表意明确而且可以使程序变得简洁&＃xff0c;而lisp的语法系统天然导致了在lisp语言中加入这两个运算符绝无可能。此外&＃xff0c;可移植的Unix操作系统的出现使另外一门同样优秀的语言——C语言——占尽了先机&＃xff0c;而此后流行的编程语言在某种程度上都有着C语言的影子。但尽管如此&＃xff0c;依然有很多人喜欢lisp&＃xff0c;因为它足够强大、足够优雅(尽管怪异)&＃xff0c;因为他们都喜欢孤独。
前面讲到&＃xff0c;如果一个表达式的表达式树已经给出&＃xff0c;那么直接对表达式树进行求值是最简单的求值方式。既然S表达式是表达式树的字符化表示&＃xff0c;那么下面就我们就来看看&＃xff0c;如何将前缀、中缀和后缀这三种表达式转化为可以存储为文本并且lisp语言可以直接进行计算的表达式树——S表达式。
表达式树的生成
表达式树的生成&＃xff0c;其过程是模拟表达式的求值过程。
前缀和后缀
(define(parse-expr get-first-operand get-second-operand)
(lambda(expr)
(letloop ([expr expr][stack &＃39;()])
(if(null?expr)
(carstack)
(let([elem (carexpr)]
[expr (cdrexpr)])
(if(operator? elem)
(let([op elem]
[first-operand (get-first-operand stack)]
[second-operand (get-second-operand stack)]
[stack (cddrstack)])
(loop expr (cons(listop first-operand second-operand) stack)))
(loop expr (conselem stack))))))))
(defineparse-suffix (parse-expr cadr car))
(defineparse-prefix (lambda(expr) ((parse-expr car cadr) (reverseexpr))))
验证一下结果的正确性
(defineassert-prefix
(lambda(expr)
(let([s-expr (parse-prefix expr)]
[value (eval-prefix expr)])
(let([s-value (evals-expr)])
(printf "prefix expr: ~a &＃61; ~a\n" expr value)
(printf " S expr: ~a &＃61; ~a\n" s-expr s-value)
(assert (&＃61;s-value value))))))
(defineassert-suffix
(lambda(expr)
(let([s-expr (parse-suffix expr)]
[value (eval-suffix expr)])
(let([s-value (evals-expr)])
(printf "suffix expr: ~a &＃61; ~a\n" expr value)
(printf " S expr: ~a &＃61; ~a\n" s-expr s-value)
(assert (&＃61;s-value value))))))![]()
中缀
(defineparse-infix
(lambda(expr)
(definecompose
(lambda(handled-expr next-expr)
(if(null?next-expr)
handled-expr
(let([op (carnext-expr)])
(caseop
[(&＃43;-) (listop handled-expr (parse-infix (cdrnext-expr)))]
[(*/) (compose (listop handled-expr (parse-infix (cadrnext-expr)))
(cddrnext-expr))])))))
(if(atom? expr)
expr
(compose (parse-infix (carexpr)) (cdrexpr)))))
可以看到&＃xff0c;表达式树的生成过程与求值过程具有相同的递归结构和执行流。
再来看一个对支持幂运算的中缀表达式的解析
(definepaser-infix
(lambda(expr)
(definesplit-high-precedence-item
(lambda(expr ops)
(let([first (paser-infix (carexpr))]
[next-expr (cdrexpr)])
(if(null?next-expr)
(valuesfirst next-expr)
(let([op (carnext-expr)])
(if(in op ops)
(let-values (([next-item next-expr]
(split-high-precedence-item (cdrnext-expr) ops)))
(values(listop first next-item) next-expr))
(valuesfirst next-expr)))))))
(definecompose
(lambda(handled-expr next-expr)
(if(null?next-expr)
handled-expr
(let([op (carnext-expr)])
(caseop
[(&＃43;-) (listop handled-expr (paser-infix (cdrnext-expr)))]
[(*/ ^)
(let-values (([next-item next-expr]
(split-high-precedence-item (cdrnext-expr) &＃39;^)))
(compose (listop handled-expr next-item) next-expr))])))))
(if(atom? expr)
expr
(compose (paser-infix (carexpr)) (cdrexpr)))))
验证一下![]()
既然可以借助栈直接对表达式进行求值&＃xff0c;那么将表达式转化为表达式树的意义何在呢&＃xff1f;这当然是非常有意义的事情&＃xff0c;将表达式转换为表达式树之后&＃xff0c;表达式树的可操作性和可计算性为表达式的优化(比如消除冗余的计算)提供了可能&＃xff0c;这对于编译优化是非常重要的。
京公网安备 11010802041100号