共计 5731 个字符,预计需要花费 15 分钟才能阅读完成。
利用递归向下算法联合咱们的 BKLexer
实现反对四则运算与括号优先级的计算器程序。
代码清单【Golang】
package main
import (
"fmt"
"os"
"bufio"
"strings"
"strconv"
"./bklexer"
)
type Node interface {GetValue() float64
}
type Number struct {value float64}
func NewNumber(token *BKLexer.Token) *Number {value, _ := strconv.ParseFloat(token.Source, 64)
return &Number{value: value}
}
func (number *Number) GetValue() float64 {return number.value}
type BinaryOpt struct {
opt string
lhs Node
rhs Node
}
func NewBinaryOpt(token *BKLexer.Token, lhs Node, rhs Node) *BinaryOpt {return &BinaryOpt{opt: token.Source, lhs: lhs, rhs: rhs}
}
func (binaryOpt *BinaryOpt) GetValue() float64 {
lhs, rhs := binaryOpt.lhs, binaryOpt.rhs
switch binaryOpt.opt {case "+": return lhs.GetValue() + rhs.GetValue()
case "-": return lhs.GetValue() - rhs.GetValue()
case "*": return lhs.GetValue() * rhs.GetValue()
case "/": return lhs.GetValue() / rhs.GetValue()
}
return 0
}
func parse(lexer *BKLexer.Lexer) Node {result := parse_binary_add(lexer)
token := lexer.GetToken()
if token.TType != BKLexer.TOKEN_TYPE_EOF {return nil}
return result
}
func parse_binary_add(lexer *BKLexer.Lexer) Node {lhs := parse_binary_mul(lexer)
if lhs == nil {return nil}
token := lexer.GetToken()
for token.Source == "+" || token.Source == "-" {rhs := parse_binary_mul(lexer)
if rhs == nil {return nil}
lhs = NewBinaryOpt(token, lhs, rhs)
token = lexer.GetToken()}
return lhs
}
func parse_binary_mul(lexer *BKLexer.Lexer) Node {lhs := parse_number(lexer)
if lhs == nil {return nil}
token := lexer.GetToken()
for token.Source == "*" || token.Source == "/" {rhs := parse_number(lexer)
if rhs == nil {return nil}
lhs = NewBinaryOpt(token, lhs, rhs)
token = lexer.GetToken()}
return lhs
}
func parse_number(lexer *BKLexer.Lexer) Node {token := lexer.NextToken()
if token.Name == "LPAR" {expr := parse_binary_add(lexer)
if expr == nil {return nil}
token := lexer.GetToken()
if token.Name != "RPAR" {return nil}
lexer.NextToken()
return expr
}
if token.Name == "NUMBER" {number := NewNumber(token)
lexer.NextToken()
return number
}
return nil
}
func main() {fmt.Println("Hello My Calc.")
lexer := BKLexer.NewLexer()
lexer.AddRule("\\d+\\.?\\d*", "NUMBER")
lexer.AddRule("\\+", "PLUS")
lexer.AddRule("-", "MINUS")
lexer.AddRule("\\*", "MUL")
lexer.AddRule("/", "DIV")
lexer.AddRule("\\(", "LPAR")
lexer.AddRule("\\)", "RPAR")
lexer.AddIgnores("[ \\f\\t]+")
reader := bufio.NewReader(os.Stdin)
for true {fmt.Print(">")
inputs, _ := reader.ReadString('\n')
inputs = strings.Trim(inputs, "\f\t\n")
if inputs == "quit" {break}
if inputs != "" {lexer.Build(inputs)
result := parse(lexer)
if result == nil {positon := lexer.GetToken().Col
fmt.Println("error in :", positon)
continue
}
fmt.Println("out =", result.GetValue())
}
}
fmt.Println("bye!")
}
运行测试
➜ go calc.go
Hello My Calc.
> 1 + (2 - 3) * 4 / 5
out = 0.19999999999999996
> quit
bye!
引入须要的包
import (
"fmt"
"os"
"bufio"
"strings"
"strconv"
"./bklexer"
)
- fmt 打印输出
- os + bufio 读取用户输出
- strings 解决字符串
- strconv 解析字符串
- bklexer 用于词法剖析
定义接口
type Node interface {GetValue() float64
}
Node
作为接口将用于指向其它的构造,其 GetValue
办法能够取得节点的数值。
定义数字节点
type Number struct {value float64}
func NewNumber(token *BKLexer.Token) *Number {value, _ := strconv.ParseFloat(token.Source, 64)
return &Number{value: value}
}
Number
作为数字类型的节点,有成员 value
用于存储数值,应用 NewNumber
函数能够实例它。
实现数字节点的接口办法
func (number *Number) GetValue() float64 {return number.value}
定义运算操作节点
type BinaryOpt struct {
opt string
lhs Node
rhs Node
}
func NewBinaryOpt(token *BKLexer.Token, lhs Node, rhs Node) *BinaryOpt {return &BinaryOpt{opt: token.Source, lhs: lhs, rhs: rhs}
}
BinaryOpt
作为运算操作节点,成员 opt
记录运算符号,lhs
、rhs
别离为表达式左、右两边的内容,如 1 + 2 中的 1 与 2。
应用 NewBinaryOpt
函数实例它。
实现运算节点的接口办法
func (binaryOpt *BinaryOpt) GetValue() float64 {
lhs, rhs := binaryOpt.lhs, binaryOpt.rhs
switch binaryOpt.opt {case "+": return lhs.GetValue() + rhs.GetValue()
case "-": return lhs.GetValue() - rhs.GetValue()
case "*": return lhs.GetValue() * rhs.GetValue()
case "/": return lhs.GetValue() / rhs.GetValue()
}
return 0
}
咱们须要依据运算操作符号 opt
判断 lhs
与rhs
的值到底以怎么的形式进行计算。
定义语法解析的入口函数
func parse(lexer *BKLexer.Lexer) Node {result := parse_binary_add(lexer)
token := lexer.GetToken()
if token.TType != BKLexer.TOKEN_TYPE_EOF {return nil}
return result
}
入口函数 parse
接管到 *BKLexer.Lexer
类型的参数后,立刻将其发送到 parse_binary_add
中,
尝试解析运算等级与加法操作雷同的运算操作。
最初判断以后 token
是否为结尾,若不是则返回 nil
否则返回解析后果。
定义加法等级运算操作的解析函数
func parse_binary_add(lexer *BKLexer.Lexer) Node {lhs := parse_binary_mul(lexer)
if lhs == nil {return nil}
token := lexer.GetToken()
for token.Source == "+" || token.Source == "-" {rhs := parse_binary_mul(lexer)
if rhs == nil {return nil}
lhs = NewBinaryOpt(token, lhs, rhs)
token = lexer.GetToken()}
return lhs
}
当函数接管到参数 lexer
并运行时会先尝试解析乘法等级的运算操作,
如果解析结束并胜利返回则判断以后 token
的字面量决定是否须要构建加法等级运算节点,
如果须要则尝试进行另一个乘法等级的运算操作解析,解析胜利则依据 opt
构建以后运算等级的节点对象。
定义乘法等级运算操作的解析函数
func parse_binary_mul(lexer *BKLexer.Lexer) Node {lhs := parse_number(lexer)
if lhs == nil {return nil}
token := lexer.GetToken()
for token.Source == "*" || token.Source == "/" {rhs := parse_number(lexer)
if rhs == nil {return nil}
lhs = NewBinaryOpt(token, lhs, rhs)
token = lexer.GetToken()}
return lhs
}
parse_binary_mul
根本和 parse_binary_add
一样,只是在运行开始是尝试解析数字或括号表达式的内容,
在判断须要构建乘法等级运算节点的时候也是尝试解析另一个数字或括号表达式的内容。
定义数字与括号表达式的解析函数
func parse_number(lexer *BKLexer.Lexer) Node {token := lexer.NextToken()
if token.Name == "LPAR" {expr := parse_binary_add(lexer)
if expr == nil {return nil}
token := lexer.GetToken()
if token.Name != "RPAR" {return nil}
lexer.NextToken()
return expr
}
if token.Name == "NUMBER" {number := NewNumber(token)
lexer.NextToken()
return number
}
return nil
}
首先获得下一个 token
,判断是否是左括号,如果是则可能为括号表达式,须要尝试进行解析,
如果解析胜利还须要判断结尾是否为右括号,全副胜利则返回解析的表达式节点,否则返回 nil
。
若一开始的 token
不是左括号而是数字则实例一个数字节点并返回。
若既不是左括号又不是数字则返回nil
。
定义词法分析器规定
lexer := BKLexer.NewLexer()
lexer.AddRule("\\d+\\.?\\d*", "NUMBER")
lexer.AddRule("\\+", "PLUS")
lexer.AddRule("-", "MINUS")
lexer.AddRule("\\*", "MUL")
lexer.AddRule("/", "DIV")
lexer.AddRule("\\(", "LPAR")
lexer.AddRule("\\)", "RPAR")
lexer.AddIgnores("[ \\f\\t]+")
循环读取用户输出并解析计算
reader := bufio.NewReader(os.Stdin)
for true {fmt.Print(">")
inputs, _ := reader.ReadString('\n')
inputs = strings.Trim(inputs, "\f\t\n")
if inputs == "quit" {break}
if inputs != "" {lexer.Build(inputs)
result := parse(lexer)
if result == nil {positon := lexer.GetToken().Col
fmt.Println("error in :", positon)
continue
}
fmt.Println("out =", result.GetValue())
}
}
fmt.Println("bye!")
当解析函数 parse
返回的内容不是 nil
时能够应用 GetValue
函数计算表达式并失去后果。
下篇《使计算器反对语句块》,欢送关注集体公众号 百晓通客栈