/
ShuntingYard.go
100 lines (89 loc) · 2.42 KB
/
ShuntingYard.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
package main
import (
"strings"
)
// Postfix struct, with precedence and association maps, and data queue
type Postfix struct {
prec map[string]int
assoc map[string]string
data []string
}
// CreatePostfix - Make a new Postfix from a string of data
func CreatePostfix(data []string) *Postfix {
// Set precedence for each operator
prec := make(map[string]int)
prec["+"] = 1
prec["-"] = 1
prec["*"] = 2
prec["/"] = 2
prec["^"] = 3
prec["k"] = 4
prec["kh"] = 4
prec["dl"] = 4
prec["d"] = 4
// Set association for each operator
assoc := make(map[string]string)
assoc["+"] = "l"
assoc["-"] = "l"
assoc["*"] = "l"
assoc["/"] = "l"
assoc["^"] = "r"
assoc["k"] = "l"
assoc["kh"] = "l"
assoc["dl"] = "l"
assoc["d"] = "l"
// Create stack for operators
opStack := []string{}
// Queue for output
outQueue := []string{}
var op string
// fmt.Println(op)
for _, char := range data {
if strings.ContainsAny(char, "1234567890") {
outQueue = append(outQueue, char)
} else if strings.Contains("+-*/dk^", string(char[0])) {
if len(opStack) > 0 {
for strings.Contains("+-*/dk^", string(opStack[len(opStack)-1][0])) &&
(prec[opStack[len(opStack)-1]] > prec[char] ||
(prec[opStack[len(opStack)-1]] == prec[char] &&
assoc[char] == "l")) &&
opStack[len(opStack)-1] != "(" {
opStack, op = Pop(opStack)
outQueue = append(outQueue, op)
}
}
opStack = append(opStack, char)
} else if char == "(" {
opStack = append(opStack, char)
} else if char == ")" {
for opStack[len(opStack)-1] != "(" {
// fmt.Println(opStack, opStack[len(opStack)-1])
opStack, op = Pop(opStack)
outQueue = append(outQueue, op)
// fmt.Println(opStack, opStack[len(opStack)-1])
// fmt.Println(outQueue)
}
if opStack[len(opStack)-1] == "(" {
opStack, op = Pop(opStack)
}
}
}
for len(opStack) > 0 {
opStack, op = Pop(opStack)
outQueue = append(outQueue, op)
}
return &Postfix{prec: prec, assoc: assoc, data: outQueue}
}
// (10d6+2d8)^2+(1d20-6d4)*12/2d4
// Output queue: 10 6 d 2 8 d + 2 ^ 1 20 d 6 4 d - 12 * 2 4 d / +
// Operator stack:
// Pop - Remove the last element of a string slice, return both that slice and the element
func Pop(stack []string) ([]string, string) {
// fmt.Println("Stack", stack)
output := string(stack[len(stack)-1])
// fmt.Println(output)
stack[len(stack)-1] = ""
stack = stack[:len(stack)-1]
// fmt.Println("Stack", stack)
return stack, output
}