盒子
盒子
文章目录
  1. Nim 编程早茶
    1. 简易计算器
      1. 分词
      2. 中缀表达式
      3. 后缀表达式

Nim 实现基于命令行的计算器

Nim 编程早茶

Nim编程实现基于命令行的计算器

https://tea.nim-cn.com/archives/

简易计算器

Nim 内置了一个更好的命令行计算器, 在命令行输入 nim secret 就可以体验了。

我们这次实现的命令行计算器,支持加减乘除、括号、浮点数、负数,以及查看历史和退出功能。

主要的思路:read - parse - print - loop。

read 阶段是指从读取用户在提示符(cal> )之后输入的字符串。

parse 阶段包括:将用户输入的字符串分割成单个对象比如:符号 +,或者数字 1.2 。其次将中缀表达式转化后缀表达式,接下来计算后缀表达式的数值。

print 阶段指的是将 parse 阶段的数值打印在终端上。

loop 阶段是指重复上述操作,除非用户输入 exit 符号或者 Ctrl + C 终止程序运行。

实现效果图:
在这里插入图片描述

为了实现后面的中缀、后缀表达式,我们需要借助栈这种数据结构。

栈是一种先进后出的数据结构,函数调用时就会使用栈来保存当前程序的地址及其他信息,前面的深度优先搜索就是基于栈实现的。

下面简单说明栈的使用:

push 函数在栈的顶部添加元素,pop 函数删除栈顶的元素,top 函数查看栈顶函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Stack*[T] = ref object
container*: seq[T]


proc len*[T](s: Stack[T]): int =
s.container.len

proc push*[T](s: Stack[T], elem: T) =
s.container.add(elem)

proc pop*[T](s: Stack[T]): T =
s.container.pop()

proc top*[T](s: Stack[T]): T =
if s.len > 0:
result = s.container[s.len - 1]

分词

分词是 parse 阶段的重要部分。

  • 我们定义符号 + - * / ( )。

  • 将这些字符串中的这些符号替换为:空格 + 符号 + 空格

1
+ => 空格+空格
  • 将字符串按空格分割,得到最终的分词

经过上述操作,就可以实现对正数以及操作符的分词功能。

1
2
3
4
5
6
7
8
9
10
iterator token*(expressions: string): string = 
var sentences: string = expressions
for symbol in symbols:
# 替换字符串
sentences = sentences.replace(symbol, fmt" {symbol} ")
var temp: seq[string]
# 分割字符串
for sentence in sentences.split:
if sentence != "":
temp.add(sentence)

为了实现对负数的分词,我们需要迭代分词序列,将‘-’ 与后面的数字转换成一个整体。我们有两种情况将 - 视作负号,第一种情况,负号位于字符串的开头;第二种情况,负号前一个符号为左括号。

1
2
3
4
5
6
7
8
9
10
11
var target: seq[string] = temp
for (i, item) in temp.pairs:
if item == "-":
# 两种情况下,当前符号设置为 ""
# 下一个符号设置为负数
if (i-1) < 0 or temp[i-1] == "(":
target[i] = ""
target[i+1] = fmt"-{target[i+1]}"
# 若字符串不为空,打印字符串
if target[i] != "":
yield target[i]

中缀表达式

中缀表达式就是我们写的各种表达式,如 3 + 2 * 4。我们希望将其转化为后缀表达式,示例如下:

1
2
中缀表达式 ==> 1 + 5 * 4 + (3 * 2 + 4) * 6
后缀表达式 ==> 1 5 4 * + 3 2 * 4 + 6 * +

我们需要准备一个栈 stack ,用于临时存放操作符;准备一个序列 seq,用来存放输出结果,也就是后缀表达式。

转化规则:

迭代分词序列,遇到数字,就将数字输出到序列 seq 中。

定义各个符号优先级,其中 乘除 > 加减 > 右括号。比较当前符号与栈顶元素的优先级,如果当前元素的优先级小于等于栈顶元素的优先级,就弹出栈顶元素,输出到 seq 序列中,然后将当前元素压入栈中。如果当前元素的优先级大于栈顶元素的优先级,或者当前元素为右括号,我们直接将当前元素压入栈中。

如果遇到左括号,我们就弹出栈中元素,并输出到 seq 序列中。其中,左右括号并不输出到序列中。

最后,将栈中剩余的符号输出到 seq 序列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 迭代 1 + 5 * 4 + (3 * 2 + 4) * 6
# 读入 1 并输出到 seq 中,将 + 压入栈中
# 读入 5 并输出到 seq 中
stack ==> +
seq ==> 1 5
# 读入 *, * 优先级 > + 优先级
# 将 * 压入栈中, 读入 4 并输出
stack ==> + *
seq ==> 1 5 4
# 读入 +, + 优先级 < * 优先级
# 将 * 输出到 seq 序列中
# + 优先级 <= + 优先级,+ 输出
# 将 + 压入栈中
stack ==> +
seq ==> 1 5 4 * +
# 读入 (, 压入栈中,读入 3,压入栈中
stack ==> + (
seq ==> 1 5 4 * + 3
# 读入 *, 压入栈中,读入 2,压入栈中
stack ==> + ( *
seq ==> 1 5 4 * + 3 2
# 读入 +,* 输出,+ 压入栈中, 4 输出
stack ==> + ( +
seq ==> 1 5 4 * + 3 2 * 4
# 读入 ),+ 输出,弹出 (
stack ==> +
seq ==> 1 5 4 * + 3 2 * 4 +
# 读入 *, 压入栈中, 6 输出
stack ==> + *
seq ==> 1 5 4 * + 3 2 * 4 + 6
# 将栈中剩余符号输出
stack ==>
seq ==> 1 5 4 * + 3 2 * 4 + 6 * +

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
proc parseInfix(expressions: string): seq[string] = 
var s: Stack[string] = Stack[string](container: @[])
var target: seq[string] = @[]
for expression in token(expressions):
let flag = (expression in symbols)
if not isFloat(expression) and not flag:
raise newException(ValueError, "error")

if isFloat(expression):
target.add(expression)

elif expression == ")":
while s.top != "(":
target.add(s.pop)
discard s.pop

elif expression == "(":
s.push(expression)

elif s.top != "" and comparePriority(expression, s.top):
target.add(s.pop)
while s.top != "" and comparePriority(expression, s.top):
target.add(s.pop)
s.push(expression)
else:
s.push(expression)

while s.len != 0:
target.add(s.pop)
result = target

后缀表达式

后缀表达式的规则:遇到数值就压入栈中;遇到符号,就从栈中弹出两个元素,计算两个元素运算结果,将得到的结果压入栈中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
proc parseSufix(expressions: seq[string]): float =
var target: float
var s: Stack[string] = Stack[string](container: @[])
for expression in expressions:
if isFloat(expression):
s.push(expression)
else:
var elem2 = parseFloat(s.pop)
var elem1 = parseFloat(s.pop)
target = evaluate(expression, elem1, elem2)
s.push(fmt"{target}")
if s.len > 0:
target = parseFloat(s.pop)
result = target

完整代码:

https://github.com/xflywind/cal