diff options
| -rw-r--r-- | defaults.go | 536 | ||||
| -rw-r--r-- | evaluator.go | 51 | ||||
| -rw-r--r-- | evaluator_test.go | 56 | ||||
| -rw-r--r-- | execute.go | 45 | ||||
| -rw-r--r-- | go.mod | 3 | ||||
| -rw-r--r-- | infixrpn.go | 104 | ||||
| -rw-r--r-- | stack.go | 27 | ||||
| -rw-r--r-- | token.go | 61 |
8 files changed, 883 insertions, 0 deletions
diff --git a/defaults.go b/defaults.go new file mode 100644 index 0000000..e68bc9b --- /dev/null +++ b/defaults.go @@ -0,0 +1,536 @@ +package expression + +import ( + "fmt" + "go/token" + "strconv" +) + +var DefaultOperators = map[token.Token]Operator{ + token.ADD: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + if !a.IsNumber() { + return fmt.Errorf("Token %s must be number", a.Literal) + } + if !b.IsNumber() { + return fmt.Errorf("Token %s must be number", b.Literal) + } + n1, isInt1 := a.Int() + n2, isInt2 := b.Int() + switch { + case isInt1 && isInt2: + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 + n1), + Pos: b.Pos, + }) + default: + stack.Push(Token{ + Token: token.FLOAT, + Literal: strconv.FormatFloat((b.Float() + a.Float()), 'g', 5, 64), + Pos: b.Pos, + }) + } + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.SUB: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + if !a.IsNumber() { + return fmt.Errorf("Token %s must be number", a.Literal) + } + if !b.IsNumber() { + return fmt.Errorf("Token %s must be number", b.Literal) + } + n1, isInt1 := a.Int() + n2, isInt2 := b.Int() + switch { + case isInt1 && isInt2: + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 - n1), + Pos: b.Pos, + }) + default: + stack.Push(Token{ + Token: token.FLOAT, + Literal: strconv.FormatFloat((b.Float() - a.Float()), 'g', 5, 64), + Pos: b.Pos, + }) + } + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.MUL: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + if !a.IsNumber() { + return fmt.Errorf("Token %s must be number", a.Literal) + } + if !b.IsNumber() { + return fmt.Errorf("Token %s must be number", b.Literal) + } + n1, isInt1 := a.Int() + n2, isInt2 := b.Int() + switch { + case isInt1 && isInt2: + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 * n1), + Pos: b.Pos, + }) + default: + stack.Push(Token{ + Token: token.FLOAT, + Literal: strconv.FormatFloat((b.Float() * a.Float()), 'g', 5, 64), + Pos: b.Pos, + }) + } + return nil + }, + priority: 20, + isLeftAssoc: false, + }, + token.QUO: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + if !a.IsNumber() { + return fmt.Errorf("Token %s must be number", a.Literal) + } + if !b.IsNumber() { + return fmt.Errorf("Token %s must be number", b.Literal) + } + n1, isInt1 := a.Int() + n2, isInt2 := b.Int() + switch { + case isInt1 && isInt2: + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 / n1), + Pos: b.Pos, + }) + default: + stack.Push(Token{ + Token: token.FLOAT, + Literal: strconv.FormatFloat((b.Float() / a.Float()), 'g', 5, 64), + Pos: b.Pos, + }) + } + return nil + }, + priority: 20, + isLeftAssoc: false, + }, + token.REM: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + if !a.IsNumber() { + return fmt.Errorf("Token %s must be number", a.Literal) + } + if !b.IsNumber() { + return fmt.Errorf("Token %s must be number", b.Literal) + } + n1, isInt1 := a.Int() + n2, isInt2 := b.Int() + switch { + case isInt1 && isInt2: + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 % n1), + Pos: b.Pos, + }) + default: + return fmt.Errorf("rem operation valid only for ints") + } + return nil + }, + priority: 20, + isLeftAssoc: false, + }, + + token.AND: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 & n1), + Pos: b.Pos, + }) + return nil + }, + priority: 20, + isLeftAssoc: false, + }, + token.OR: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 | n1), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.XOR: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 ^ n1), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.SHL: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 << n1), + Pos: b.Pos, + }) + return nil + }, + priority: 30, + isLeftAssoc: false, + }, + token.SHR: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(n2 >> n1), + Pos: b.Pos, + }) + return nil + }, + priority: 30, + isLeftAssoc: false, + }, + + token.LAND: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n1 != 0 && n2 != 0 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + + return nil + }, + priority: 20, + isLeftAssoc: false, + }, + token.LOR: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n1 != 0 || n2 != 0 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.EQL: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + r := 0 + if a.Literal == b.Literal { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.LSS: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n2 < n1 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.GTR: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n2 > n1 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.NEQ: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + r := 0 + if a.Literal != b.Literal { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.LEQ: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n2 <= n1 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.GEQ: { + fn: func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := 0 + if n2 >= n1 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + priority: 10, + isLeftAssoc: false, + }, + token.NOT: { + fn: func(stack *Stack) error { + a := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + r := 0 + if n1 == 0 { + r = 1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: a.Pos, + }) + + return nil + }, + priority: 40, + isLeftAssoc: false, + }, +} + +var DefaultFunctions = map[string]func(stack *Stack) error{ + "max": func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := n2 + if n2 < n1 { + r = n1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, + "min": func(stack *Stack) error { + a := stack.Pop() + b := stack.Pop() + n1, isInt1 := a.Int() + if !isInt1 { + return fmt.Errorf("Token %s must be integer", a.Literal) + } + n2, isInt2 := b.Int() + if !isInt2 { + return fmt.Errorf("Token %s must be integer", b.Literal) + } + r := n2 + if n2 > n1 { + r = n1 + } + stack.Push(Token{ + Token: token.INT, + Literal: strconv.Itoa(r), + Pos: b.Pos, + }) + return nil + }, +} diff --git a/evaluator.go b/evaluator.go new file mode 100644 index 0000000..486d45f --- /dev/null +++ b/evaluator.go @@ -0,0 +1,51 @@ +package expression + +import ( + "go/scanner" + "go/token" +) + +type Evaluator struct { + operators map[token.Token]Operator + functions map[string]func(stack *Stack) error +} + +func New() *Evaluator { + return &Evaluator{ + operators: DefaultOperators, + functions: DefaultFunctions, + } +} + +func (e *Evaluator) Eval(expression string) (any, error) { + s := scanner.Scanner{} + fset := token.NewFileSet() + file := fset.AddFile("", fset.Base(), len(expression)) + s.Init(file, []byte(expression), nil, scanner.ScanComments) + tokens := make(chan Token) + go func() { + for { + pos, tok, lit := s.Scan() + if tok == token.SEMICOLON { + continue + } + if tok == token.EOF { + break + } + tokens <- Token{ + Token: tok, + Literal: lit, + Pos: int(pos), + } + } + close(tokens) + }() + rpnTokens := e.ToPRN(tokens) + return e.execute(rpnTokens) +} + +type Operator struct { + fn func(stack *Stack) error + priority int + isLeftAssoc bool +} diff --git a/evaluator_test.go b/evaluator_test.go new file mode 100644 index 0000000..8c956a6 --- /dev/null +++ b/evaluator_test.go @@ -0,0 +1,56 @@ +package expression + +import ( + "reflect" + "testing" +) + +func TestEvaluator_Eval(t *testing.T) { + type args struct { + expression string + } + tests := []struct { + name string + args args + want any + wantErr bool + }{ + { + name: "simple math", + args: args{ + expression: "2 + 2 * 2 + max(4,9)", + }, + want: 2 + 2*2 + 9, + wantErr: false, + }, + { + name: "simple math 2", + args: args{ + expression: "10 % 5", + }, + want: 10 % 5, + wantErr: false, + }, + { + name: "simple math 3", + args: args{ + expression: "10 / 5", + }, + want: 10 / 5, + wantErr: false, + }, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + e := New() + got, err := e.Eval(tt.args.expression) + if (err != nil) != tt.wantErr { + t.Errorf("Evaluator.Eval() error = %v, wantErr %v", err, tt.wantErr) + return + } + if !reflect.DeepEqual(got, tt.want) { + t.Errorf("Evaluator.Eval() = %v, want %v", got, tt.want) + } + }) + } +} diff --git a/execute.go b/execute.go new file mode 100644 index 0000000..8062d32 --- /dev/null +++ b/execute.go @@ -0,0 +1,45 @@ +package expression + +import ( + "fmt" + "go/token" + "strings" +) + +func (e *Evaluator) execute(tokens chan Token) (any, error) { + stack := Stack{} + for tok := range tokens { + switch { + case tok.IsNumber(): + stack.Push(tok) + case tok.IsOperator(): + op := e.operators[tok.Token] + if err := op.fn(&stack); err != nil { + return nil, err + } + case tok.IsFunc(): + fn, fnEsist := e.functions[strings.ToLower(tok.Literal)] + if !fnEsist { + return nil, fmt.Errorf("unknown function %s at %d", tok.Literal, tok.Pos) + } + if err := fn(&stack); err != nil { + return nil, err + } + case tok.IsError(): + return nil, fmt.Errorf("Error at token %d: %w", tok.Pos, tok.Error()) + } + } + if len(stack) != 1 { + return nil, fmt.Errorf("Expected exact one returning value, go %+v", stack) + } + result := stack.Pop() + switch result.Token { + case token.INT: + n, _ := result.Int() + return n, nil + case token.FLOAT: + return result.Float(), nil + default: + return result.Literal, nil + } +} @@ -0,0 +1,3 @@ +module go.neonxp.dev/expression + +go 1.18 diff --git a/infixrpn.go b/infixrpn.go new file mode 100644 index 0000000..18dde39 --- /dev/null +++ b/infixrpn.go @@ -0,0 +1,104 @@ +package expression + +import ( + "fmt" + "go/token" +) + +func (e *Evaluator) ToPRN(in <-chan Token) chan Token { + out := make(chan Token) + stack := &Stack{} + + go func() { + defer func() { + for !stack.Empty() { + tok := stack.Pop() + if tok.LP() { + out <- Token{ + Token: token.ILLEGAL, + Literal: "no closing parenthesis", + Pos: tok.Pos, + } + } else { + out <- tok + } + } + close(out) + }() + for tok := range in { + switch { + case tok.Token == token.ILLEGAL: + return + case tok.IsNumber(): + out <- tok + case tok.IsFunc(): + stack.Push(tok) + case tok.IsSeparator(): + for { + if stack.Empty() { + out <- Token{ + Token: token.ILLEGAL, + Literal: "no opening parenthesis", + Pos: tok.Pos, + } + return + } + if stack.Head().LP() { + break + } + out <- tok + } + case tok.IsOperator(): + op1 := e.operators[tok.Token] + for { + if stack.Empty() { + break + } + if stack.Head().IsOperator() { + op2, hasOp := e.operators[stack.Head().Token] + if !hasOp { + out <- Token{ + Token: token.ILLEGAL, + Literal: fmt.Sprintf("unknown operator: %s", stack.Head().Literal), + Pos: tok.Pos, + } + return + } + if op2.priority > op1.priority { + out <- stack.Pop() + continue + } else { + break + } + } else { + break + } + } + stack.Push(tok) + case tok.LP(): + stack.Push(tok) + case tok.RP(): + for { + if stack.Empty() { + out <- Token{ + Token: token.ILLEGAL, + Literal: "no opening parenthesis", + Pos: tok.Pos, + } + return + } + if stack.Head().LP() { + break + } + out <- tok + } + stack.Pop() + if stack.Head().IsFunc() { + out <- stack.Pop() + } + } + } + }() + + return out +} diff --git a/stack.go b/stack.go new file mode 100644 index 0000000..c0850d4 --- /dev/null +++ b/stack.go @@ -0,0 +1,27 @@ +package expression + +type Stack []Token + +func (s *Stack) Push(item Token) { + *s = append(*s, item) +} + +func (s *Stack) Pop() (item Token) { + if len(*s) == 0 { + return + } + + *s, item = (*s)[:len(*s)-1], (*s)[len(*s)-1] + return item +} + +func (s *Stack) Empty() bool { + return len(*s) == 0 +} + +func (s *Stack) Head() (item *Token) { + if s.Empty() { + return nil + } + return &((*s)[len(*s)-1]) +} diff --git a/token.go b/token.go new file mode 100644 index 0000000..17ff6bd --- /dev/null +++ b/token.go @@ -0,0 +1,61 @@ +package expression + +import ( + "fmt" + "go/token" + "strconv" +) + +type Token struct { + Token token.Token + Literal string + Pos int +} + +func (t *Token) Int() (int, bool) { + if t.Token != token.INT { + return 0, false + } + i, _ := strconv.Atoi(t.Literal) + return i, true +} + +func (t *Token) Float() float64 { + i, _ := strconv.ParseFloat(t.Literal, 64) + return i +} + +func (t *Token) IsNumber() bool { + return t.Token == token.INT || t.Token == token.FLOAT +} + +func (t *Token) LP() bool { + return t.Token == token.LPAREN +} + +func (t *Token) RP() bool { + return t.Token == token.RPAREN +} + +func (t *Token) IsFunc() bool { + return t.Token == token.IDENT +} + +func (t *Token) IsSeparator() bool { + return t.Token == token.COMMA +} + +func (t *Token) IsOperator() bool { + return t.Token.IsOperator() && !t.LP() && !t.RP() +} + +func (t *Token) IsError() bool { + return t.Token != token.ILLEGAL +} + +func (t *Token) Error() error { + if t.Token != token.ILLEGAL { + return nil + } + return fmt.Errorf(t.Literal) +} |