Recursive down algorithm implements calculator

Using recursive down algorithm combined with our Bklexer implementation to support four operations and bracket priority calculator program.

【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!" )}

Run the test

➜ go calc. Go Hello My calc. > 1 + (2-3) * 4/5 out = 0.1999999999999999996 > quit bye!

Introduce the required packages

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
    "./bklexer"
)

• FMT printout
• OS + Bufio reads user input
• Strings handles strings
• Strconv parses strings
• Bklexer is used for lexical analysis

Defines the interface

type Node interface {
    GetValue() float64
}

Node is used as an interface to point to other structures, and its getValue method gets the value of the Node.

Define digital nodes

type Number struct {
    value float64
}

func NewNumber(token *BKLexer.Token) *Number {
    value, _ := strconv.ParseFloat(token.Source, 64)
    return &Number{value: value}
}

Number is a node of numeric type that has a member value for storing the value, which can be instantiated using the newNumber function.

Implement interface methods for digital nodes

func (number *Number) GetValue() float64 {
    return number.value
}

Define operation nodes

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 is used as the operation node. The member opt records the operation symbol. Lhs and RHS are the contents of the left and right sides of the expression respectively, such as 1 and 2 in 1+2. Instance it using the newBinaryOpt function.

Implement interface methods for computing nodes

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
}

We need to judge how to calculate the values of LHS and RHS according to the operation symbol OPT.

Define entry functions for syntax parsing

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 }

The entry function parse receives an argument of type * bklexer.lexer and immediately sends it to parse_binary_add to attempt to parse operations that have the same level of operation as the addition operation. Finally, determine whether the current token is terminated. If not, return nil or return the parsing result.

Defines the analytic function of the addition level operation

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
}

When the function receives the lexer parameter and runs, it will first attempt to parse the multiplication level operation operation. If the parsing is completed and successfully returns, it will judge the literal value of the current token to determine whether the addition level operation node needs to be built. If so, it will try to parse another multiplication level operation operation. If the parsing is successful, the node object of the current operation level is constructed according to OPT.

Defines the analytic function of the multiplication rank operation

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 is basically the same as parse_binary_add, except that it tries to parse the contents of a number or parenthesis expression at the beginning of the run, and it also tries to parse the contents of another number or parenthesis expression when it determines that the multiplication rank node needs to be built.

Defines analytic functions for numeric and parenthesis expressions

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 }

If it is, it may be a parenthesis expression, and you need to attempt to parse it. If the parse is successful, you need to determine if the end of the parse is a parenthesis. If all succeed, the parsed expression node is returned, otherwise nil is returned. If the initial token is not an opening parenthesis but a number, then a number node is instantiated and returned. Returns nil if it is neither an open parenthesis nor a number.

Define lexer rules

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]+")

Loop through user input and parse the calculation

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!" )

The getValue function can be used to evaluate the expression and get the result when the parse function returns something other than nil.

The next section “make calculator support statement block”, welcome to pay attention to the individual public number Baixiao Tong Inn