/
shunting_yard.go
138 lines (112 loc) · 2.91 KB
/
shunting_yard.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package arithmetic
import (
"fmt"
)
// shunting yard algorithm: transforms an input from infix to postfix notation.
func shuntingYard(input []interface{}) ([]interface{}, error) {
os := &stack{}
as := &stack{}
var output []interface{}
// Read each token and look at the type.
for _, token := range input {
switch v := token.(type) {
// If it is a function, push it to the operator stack and increment the arity stack.
case function:
as.push(1)
os.push(v)
// If it is an operator, pop each operator and function with
// until an operator with a lower precedence is encountered.
// Put those values to the output.
// If a function is popped, pop the arity stack to the output before the operator.
// Then, push the operator to the stack.
case operator:
op := v
for {
v, ok := os.pop()
if !ok {
break
}
if v, ok := v.(operator); ok {
if v.precedence() >= op.precedence() {
output = append(output, v)
continue
}
}
if v, ok := v.(function); ok {
p, _ := as.pop()
output = append(output, p)
output = append(output, v)
continue
}
os.push(v)
break
}
os.push(v)
// If a left parenthesis is encoutered, push it to the operator stack.
case leftParenthesis:
os.push(v)
// If a right parenthesis is encountered, pop the operator stack until a left parenthesis
// is encountered. If the parenthesis belongs to a function, pop the function too.
// Then, push the operator to the stack.
case rightParenthesis:
for {
v, ok := os.pop()
if !ok {
return nil, fmt.Errorf("invalid expression: %v", input)
}
if _, ok := v.(leftParenthesis); ok {
v, ok := os.pop()
if !ok {
break
}
if v, ok := v.(function); ok {
p, _ := as.pop()
output = append(output, p, v)
break
}
os.push(v)
break
}
output = append(output, v)
}
// If a comma is encountered, pop the operator stack until a left panrethesis is encountered. If the parenthesis belongs to a function, pop the function too.
case comma:
as.inc()
for {
v, ok := os.pop()
if !ok {
return nil, fmt.Errorf("invalid expression: %v", input)
}
if v, ok := v.(leftParenthesis); ok {
os.push(v)
break
}
if _, ok := v.(function); ok {
p, _ := as.pop()
output = append(output, p)
}
output = append(output, v)
}
// If an operand is encountered, append it to the output.
default:
output = append(output, v)
}
}
// Once the input has been read, pop the operator stack. When a function is encountered, pop
// the arity stack.
for {
v, ok := os.pop()
if !ok {
break
}
if _, ok := v.(leftParenthesis); ok {
return nil, fmt.Errorf("mismatched parenthesis: %v", input)
}
if _, ok := v.(function); ok {
p, _ := as.pop()
output = append(output, p)
}
output = append(output, v)
}
return output, nil
}