-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathinfix.go
151 lines (130 loc) · 2.88 KB
/
infix.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
139
140
141
142
143
144
145
146
147
148
149
150
151
package main
import (
"fmt"
"os"
)
type RuneStack struct {
runes []rune
}
func (s *RuneStack) Pop() rune {
end := len(s.runes)
if end < 1 {
fmt.Println("Invalid pop")
os.Exit(-1)
}
r := s.runes[end - 1]
s.runes = s.runes[:(end - 1)] // Chop off the last element.
return r}
func (s *RuneStack) Push(r rune) {
s.runes = append(s.runes, r)
}
func (s *RuneStack) Size() int {
return len(s.runes)
}
type IntStack struct {
values []int
}
func (s *IntStack) Pop() int {
end := len(s.values)
if end < 1 {
fmt.Println("Invalid pop")
os.Exit(-1)
}
value := s.values[end - 1]
s.values = s.values[:(end - 1)] // Chop off the last element.
return value
}
func (s *IntStack) Push(i int) {
s.values = append(s.values, i)
}
func (s *IntStack) Size() int {
return len(s.values)
}
func intify(r rune) int {
return int(r - '0')
}
func runify(i int) rune {
return rune(i + '0')
}
func operate(op rune, op1 int, op2 int) int {
if op == '/' {
return op2 / op1 // Reversed order because of stack.
} else if op == '*' {
return op1 * op2
} else if op == '-' {
return op2 - op1
} else { // Must be addition.
return op1 + op2
}
}
func isInt(r rune) bool {
i := intify(r)
if i > -1 && i < 10 { // Going rune by rune these are the only valid nums.
return true
} else {
return false
}
}
func (s *IntStack) flattenToNum() int {
if s.Size() == 0 {
fmt.Println("Can't call flattenToNum on empty stack")
os.Exit(-1)
}
multiplier := 1
total := 0
for s.Size() > 0 {
total += s.Pop() * multiplier
multiplier *= 10
}
return total
}
func pushComputation(valueStack *IntStack, opStack *RuneStack) {
nextOp := opStack.Pop()
operand1 := valueStack.Pop()
operand2 := valueStack.Pop()
result := operate(nextOp, operand1, operand2)
valueStack.Push(result)
}
func compute(expression string) int {
valueStack := new(IntStack)
opStack := new(RuneStack)
digitBuffer := new(IntStack)
for _,r := range expression {
if r == ')' {
// Flush the int buffer.
if digitBuffer.Size() > 0 {
value := digitBuffer.flattenToNum()
valueStack.Push(value)
}
pushComputation(valueStack, opStack)
} else if (r == '+' || r == '-' || r == '*' || r == '/') {
opStack.Push(r)
// Flush the int buffer.
if digitBuffer.Size() > 0 {
value := digitBuffer.flattenToNum()
valueStack.Push(value)
}
} else if (isInt(r)) {
digitBuffer.Push(intify(r)) // Push onto buffer
}
}
// Flush the buffer one last time.
if digitBuffer.Size() > 0 {
value := digitBuffer.flattenToNum()
valueStack.Push(value)
}
// Handle case with no outer parens
if valueStack.Size() == 2 && opStack.Size() == 1 {
pushComputation(valueStack, opStack)
}
if valueStack.Size() > 1 || opStack.Size() != 0 {
fmt.Println("Invalid expression")
os.Exit(-1)
}
return valueStack.Pop()
}
func main() {
expression := "((10 * 5) + 7) + 2) / 5"
answer := compute(expression)
fmt.Println(answer)
}