乐趣区

关于golang:递归向下算法实现计算器

jiezi

利用递归向下算法联合咱们的 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 函数计算表达式并失去后果。

下篇《使计算器反对语句块》，欢送关注集体公众号 百晓通客栈

退出移动版