Anonymous user
Arithmetic Evaluator/Go: Difference between revisions
→Operator precedence parser
(Created) |
imported>Katsumi |
||
| (4 intermediate revisions by one other user not shown) | |||
Line 1:
__TOC__
=Operator precedence parser=
This is an operator precedence parser. The number format used in calculation can be changed with the line "type Number int".
<
import (
Line 14:
/* ==== AST ==== */
type Number
type Node interface {
Line 228:
}
}
</syntaxhighlight>
<pre>
Line 243:
</pre>
== 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:
<pre>
(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'
</pre>
| |||