Arithmetic Evaluator/Go
Operator precedence parser
This is an operator precedence parser. The number format used in calculation can be changed with the line "type Number int".
<lang go>package main
import (
"bufio" "fmt" "os" "strings"
)
/* ==== AST ==== */
type Number float64
type Node interface {
Eval() (Number,bool)
}
// Binary operator AST node type Binary struct {
op byte left Node right Node
}
func (n *Binary) Init(op byte, left, right Node) Node {
n.op = op n.left = left n.right = right return n
}
func (n *Binary) Eval() (Number,bool) {
left, ok := n.left.Eval()
if !ok { return 0, false }
right, ok := n.right.Eval()
if !ok { return 0, false }
switch n.op {
case '+': return left + right, true
case '-': return left - right, true
case '*': return left * right, true
case '/':
if right == 0 { return 0, false }
return left / right, true
}
return 0, false
}
func (n *Binary) String() string {
return fmt.Sprintf("(%s %c %s)", n.left, n.op, n.right)
}
// Leaf value AST node type Leaf struct {
value Number
}
func (n *Leaf) Init(value Number) Node {
n.value = value return n
}
func (n *Leaf) Eval() (Number,bool) {
return n.value,true
}
func (n *Leaf) String() string {
return fmt.Sprintf("%v", n.value) // %v = default format
}
/* ==== Lexer ==== */
type Lexer struct {
data string pos int Kind int Num Number Oper byte
}
const (
ERR = iota // error NUM // number LPAR // left parenthesis RPAR // right parenthesis OP // operator
)
func (lexer *Lexer) Init(data string) *Lexer {
lexer.data = data lexer.pos = 0 return lexer
}
func (l *Lexer) Next() int {
n := len(l.data)
l.Kind = ERR
if l.pos < n {
switch char := l.data[l.pos]; char {
case '+', '-', '*', '/':
l.pos++
l.Kind = OP
l.Oper = char
case '(':
l.pos++
l.Kind = LPAR
l.Oper = char
case ')':
l.pos++
l.Kind = RPAR
l.Oper = char
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.':
var value Number = 0
var divisor Number = 1
for ; l.pos < n && '0' <= l.data[l.pos] && l.data[l.pos] <= '9'; l.pos++ {
value = value * 10 + Number(l.data[l.pos] - '0')
}
if l.pos < n && l.data[l.pos] == '.' {
l.pos++
for ; l.pos < n && '0' <= l.data[l.pos] && l.data[l.pos] <= '9'; l.pos++ {
value = value * 10 + Number(l.data[l.pos] - '0')
divisor *= 10
}
}
l.Kind = NUM
l.Num = value / divisor
}
}
return l.Kind
}
/* ==== Parser ==== */
type Parser struct {
lexer *Lexer precedence map[byte] int
}
func (p *Parser) Init(data string) *Parser {
p.lexer = new(Lexer).Init(data) p.precedence = make(map[byte] int) p.lexer.Next() return p
}
func (p *Parser) AddOperator(op byte, precedence int) {
p.precedence[op] = precedence
}
func (p *Parser) Parse() (Node,bool) {
lhs, ok := p.parsePrimary()
if !ok { return nil, false }
// starting with 1 instead of 0, because
// map[*]int returns 0 for non-existant items
node, ok := p.parseOperators(lhs, 1)
if !ok { return nil, false }
return node, true
}
func (p *Parser) parsePrimary() (Node,bool) {
switch p.lexer.Kind {
case NUM:
node := new(Leaf).Init(p.lexer.Num)
p.lexer.Next()
return node, true
case LPAR:
p.lexer.Next()
node, ok := p.Parse()
if (!ok) { return nil, false }
if p.lexer.Kind == RPAR { p.lexer.Next() }
return node, true
}
return nil, false
}
func (p *Parser) parseOperators(lhs Node, min_precedence int) (Node,bool) {
var ok bool
var rhs Node
for p.lexer.Kind == OP && p.precedence[p.lexer.Oper] >= min_precedence {
op := p.lexer.Oper
p.lexer.Next()
rhs, ok = p.parsePrimary()
if (!ok) { return nil, false }
for p.lexer.Kind == OP && p.precedence[p.lexer.Oper] > p.precedence[op] {
op2 := p.lexer.Oper
rhs, ok = p.parseOperators(rhs, p.precedence[op2])
if (!ok) { return nil, false }
}
lhs = new(Binary).Init(op,lhs,rhs)
}
return lhs, true
}
/* ==== Test ==== */
func main() {
var node Node
var result Number
var p *Parser
var parseOk, evalOk bool
in := bufio.NewReader(os.Stdin)
line, ioErr := in.ReadString('\n')
for len(line) > 0 {
line = strings.TrimSpace(line)
fmt.Printf("Read: %q\n", line) // %q = quoted string
p = new(Parser).Init(line)
p.AddOperator('+',1)
p.AddOperator('-',1)
p.AddOperator('*',2)
p.AddOperator('/',2)
node, parseOk = p.Parse()
if parseOk {
fmt.Printf("Parsed: %s\n", node)
result, evalOk = node.Eval()
if evalOk {
fmt.Printf("Evaluated: %v\n", result) // %v = default format
} else {
fmt.Printf("%s = Evaluation error\n", line)
}
} else {
fmt.Printf("%s = Syntax error\n", line)
}
if ioErr != nil { return }
line, ioErr = in.ReadString('\n')
}
} </lang>
Example
1+2*3 Read: "1+2*3" Parsed: (1 + (2 * 3)) Evaluated: 7 (1+2)*(3+4)*(5+6) Read: "(1+2)*(3+4)*(5+6)" Parsed: (((1 + 2) * (3 + 4)) * (5 + 6)) Evaluated: 231
External links
Library
Shown here is use of the package go/parser in the standard library. For the Go 1 release, there is a parser in the standard library, but not an evaluator. Evaluation is relatively easy though, once you have a parse tree.
Go expressions can be more complex than what is required for the task. These will parse but then are caught and disallowed in the evaluator. <lang go>package main
import (
"errors" "fmt" "go/ast" "go/parser" "go/token" "reflect" "strconv"
)
var tests = []string{
"(1+3)*7", // 28, example from task description. "1+3*7", // 22, shows operator precedence. "7", // 7, a single literal is a valid expression. "7/3", // eval only does integer math. "7.3", // this parses, but we disallow it in eval. "7^3", // parses, but disallowed in eval. "go", // a valid keyword, not valid in an expression. "3@7", // error message is "illegal character." "", // EOF seems a reasonable error message.
}
func main() {
for _, exp := range tests {
if r, err := parseAndEval(exp); err == nil {
fmt.Println(exp, "=", r)
} else {
fmt.Printf("%s: %v\n", exp, err)
}
}
}
func parseAndEval(exp string) (int, error) {
tree, err := parser.ParseExpr(exp)
if err != nil {
return 0, err
}
return eval(tree)
}
func eval(tree ast.Expr) (int, error) {
switch n := tree.(type) {
case *ast.BasicLit:
if n.Kind != token.INT {
return unsup(n.Kind)
}
i, _ := strconv.Atoi(n.Value)
return i, nil
case *ast.BinaryExpr:
switch n.Op {
case token.ADD, token.SUB, token.MUL, token.QUO:
default:
return unsup(n.Op)
}
x, err := eval(n.X)
if err != nil {
return 0, err
}
y, err := eval(n.Y)
if err != nil {
return 0, err
}
switch n.Op {
case token.ADD:
return x + y, nil
case token.SUB:
return x - y, nil
case token.MUL:
return x * y, nil
case token.QUO:
return x / y, nil
}
case *ast.ParenExpr:
return eval(n.X)
}
return unsup(reflect.TypeOf(tree))
}
func unsup(i interface{}) (int, error) {
return 0, errors.New(fmt.Sprintf("%v unsupported", i))
}</lang> Output:
(1+3)*7 = 28 1+3*7 = 22 7 = 7 7/3 = 2 7.3: FLOAT unsupported 7^3: ^ unsupported go: 1:1: expected operand, found 'go' 3@7: 1:2: illegal character U+0040 '@' : 1:1: expected operand, found 'EOF'