-
Notifications
You must be signed in to change notification settings - Fork 2
/
notation.go
385 lines (319 loc) · 11.1 KB
/
notation.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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
/*
抽象構文木の中置表記生成処理のパッケージ。
抽象構文木の中置表記は、BCDiceコマンドの実行結果のメッセージに含まれる。
中置表記を表示することで、利用者が入力したコマンドが構文解析器に正しく解釈されていることを示すことができる。
この中置表記は、日常的に数式で使われている、最小限の括弧を含むものとする。
*/
package notation
import (
"bytes"
"fmt"
"strings"
"github.com/raa0121/GoBCDice/pkg/core/ast"
"github.com/raa0121/GoBCDice/pkg/core/util"
)
// InfixNotation は構文解析木の中置表記を返す。
//
// node: 構文解析木のルートノード,
// walkingToLeft: 左側への探索を続けているか。
//
// walkingToLeft は、単項マイナスを括弧で囲むかどうかの決定に使われる。
// 括弧で囲まれた範囲のルートノードから連続して左側を調べていき、
// 最左端が単項マイナスであれば括弧で囲まないように、そうでなければ
// 括弧で囲むようにしている。
// この最左端かどうかの判定にwalkingToLeftを使っている。
// ルートノードに対してこの関数を呼び出すときはwalkingToLeftをtrueに
// 設定し、右側の中置表記を求める際にはfalseを設定する。
func InfixNotation(node ast.Node, walkingToLeft bool) (string, error) {
switch n := node.(type) {
case *ast.BRollList:
return infixNotationOfBRollList(n)
case *ast.RRollList:
return infixNotationOfRRollList(n)
case *ast.URollExpr:
return infixNotationOfURollExpr(n)
case *ast.Choice:
return infixNotationOfChoice(n)
case *ast.Command:
return infixNotationOfCommand(n, walkingToLeft)
case *ast.Divide:
return infixNotationOfDivide(n, walkingToLeft)
case ast.PrefixExpression:
return infixNotationOfPrefixExpression(n, walkingToLeft)
case ast.InfixExpression:
switch n.Type() {
case ast.COMPARE_NODE:
return infixNotationOfCompare(n)
case ast.RANDOM_NUMBER_NODE:
return infixNotationOfRandomNumber(n)
default:
return infixNotationOfInfixExpression(n, walkingToLeft)
}
case *ast.Int:
return fmt.Sprintf("%d", n.Value), nil
case *ast.SumRollResult:
return infixNotationOfSumRollResult(n)
}
return "", fmt.Errorf("infix notation not implemented: %s", node.Type())
}
// infixNotationOfCommand はコマンドの中置表記を返す。
func infixNotationOfCommand(node *ast.Command, walkingToLeft bool) (string, error) {
switch node.Type() {
case ast.CALC_NODE:
return infixNotationOfCalc(node)
default:
return infixNotationOfNormalCommand(node, walkingToLeft)
}
}
// infixNotationOfNormalCommand は通常のコマンドの中置表記を返す。
func infixNotationOfNormalCommand(node *ast.Command, walkingToLeft bool) (string, error) {
expr, err := InfixNotation(node.Expression, walkingToLeft)
if err != nil {
return "", err
}
return expr, nil
}
// infixNotationOfCalc は計算ノードの中置表記を返す。
func infixNotationOfCalc(node *ast.Command) (string, error) {
expr, err := InfixNotation(node.Expression, true)
if err != nil {
return "", err
}
return fmt.Sprintf("C(%s)", expr), nil
}
// infixNotationOfBRollList はバラバラロール列の中置表記を返す。
func infixNotationOfBRollList(node *ast.BRollList) (string, error) {
infixNotations := make([]string, 0, len(node.BRolls))
for _, b := range node.BRolls {
n, err := InfixNotation(b, true)
if err != nil {
return "", err
}
infixNotations = append(infixNotations, n)
}
return strings.Join(infixNotations, "+"), nil
}
// infixNotationOfRRollList は個数振り足しロール列の中置表記を返す。
func infixNotationOfRRollList(node *ast.RRollList) (string, error) {
var out bytes.Buffer
infixNotations := make([]string, 0, len(node.RRolls))
for _, r := range node.RRolls {
n, err := InfixNotation(r, true)
if err != nil {
return "", err
}
infixNotations = append(infixNotations, n)
}
out.WriteString(strings.Join(infixNotations, "+"))
if !node.Threshold.IsNil() {
infixNotationOfThreshold, err := InfixNotation(node.Threshold, true)
if err != nil {
return "", err
}
out.WriteString("[")
out.WriteString(infixNotationOfThreshold)
out.WriteString("]")
}
return out.String(), nil
}
// infixNotationOfURollExpr は上方無限ロール式の中置表記を返す。
func infixNotationOfURollExpr(node *ast.URollExpr) (string, error) {
if node.Bonus == nil {
uRollListNotation, uRollListNotationErr :=
InfixNotation(node.URollList, true)
if uRollListNotationErr != nil {
return "", uRollListNotationErr
}
return uRollListNotation, nil
}
// 以下はボーナスが指定されていたときの中置表記生成処理
// ボーナスのノードのコピーを作る
copiedBonus := util.Clone(node.Bonus).(ast.BasicInfixExpression)
// ボーナスのノードの左側はnilになっているので、URollListを設定する
copiedBonus.SetLeft(node.URollList)
bonusInfixNotation, bonusInfixNotationErr :=
InfixNotation(&copiedBonus, true)
if bonusInfixNotationErr != nil {
return "", bonusInfixNotationErr
}
return bonusInfixNotation, nil
}
func infixNotationOfChoice(node *ast.Choice) (string, error) {
itemValues := make([]string, 0, len(node.Items))
for _, item := range node.Items {
itemValues = append(itemValues, item.Value)
}
var out bytes.Buffer
out.WriteString("CHOICE[")
out.WriteString(strings.Join(itemValues, ","))
out.WriteString("]")
return out.String(), nil
}
// infixNotationOfCompare は比較式の中置表記を返す。
func infixNotationOfCompare(node ast.InfixExpression) (string, error) {
leftInfixNotation, leftErr := InfixNotation(node.Left(), true)
if leftErr != nil {
return "", leftErr
}
rightInfixNotation, rightErr := InfixNotation(node.Right(), true)
if rightErr != nil {
return "", rightErr
}
return leftInfixNotation + node.Operator() + rightInfixNotation, nil
}
// infixNotationOfPrefixExpression は前置式の中置表記を返す。
func infixNotationOfPrefixExpression(node ast.PrefixExpression, walkingToLeft bool) (string, error) {
right := node.Right()
if right.IsPrimaryExpression() {
// 一次式の場合は括弧で囲まない
rightInfixNotation, err := InfixNotation(right, walkingToLeft)
if err != nil {
return "", err
}
return node.Operator() + rightInfixNotation, nil
}
// 一次式でない場合は括弧で囲む
rightInfixNotation, err := InfixNotation(right, true)
if err != nil {
return "", err
}
return node.Operator() + Parenthesize(rightInfixNotation), nil
}
// parenthesizeChildOfInfixExpression は中置式の子ノードの中置表記を返す。
// 必要な場合は子ノードの中置表記を括弧で囲む。
//
// parent: 中置式のノード,
// child: 中置式の子ノード,
// parentIsAssociative: 中置式が子ノードの方向に結合性かどうか。
func parenthesizeChildOfInfixExpression(
parent ast.InfixExpression,
child ast.Node,
parentIsAssociative bool,
walkingToLeft bool,
) (string, error) {
switch c := child.(type) {
case ast.PrefixExpression:
{
infixNotationOfChild, err := InfixNotation(child, walkingToLeft)
if err != nil {
return "", err
}
return Parenthesize(infixNotationOfChild), nil
}
case ast.InfixExpression:
{
lowPrecedence := c.Precedence() < parent.Precedence()
samePrecedenceAndNonAssociative :=
c.Precedence() == parent.Precedence() && !parentIsAssociative
if lowPrecedence || samePrecedenceAndNonAssociative {
infixNotationOfChild, err := InfixNotation(child, true)
if err != nil {
return "", err
}
return Parenthesize(infixNotationOfChild), nil
}
infixNotationOfChild, err := InfixNotation(child, walkingToLeft)
if err != nil {
return "", err
}
return infixNotationOfChild, nil
}
default:
{
infixNotationOfChild, err := InfixNotation(child, walkingToLeft)
if err != nil {
return "", err
}
return infixNotationOfChild, nil
}
}
}
// Parenthesize は文字列を括弧で囲む。
func Parenthesize(s string) string {
return "(" + s + ")"
}
// infixNotationOfInfixExpression は中置式の中置表記を返す。
func infixNotationOfInfixExpression(node ast.InfixExpression, walkingToLeft bool) (string, error) {
left, right, err := infixNotationsOfInfixExpressionChildren(node, walkingToLeft)
if err != nil {
return "", err
}
return left + node.Operator() + right, nil
}
// infixNotationOfDivide は除算の中置表記を返す。
// 除算では端数処理の方法を除数の後で示す必要があるため、処理が特別になる。
func infixNotationOfDivide(node *ast.Divide, walkingToLeft bool) (string, error) {
left, right, err := infixNotationsOfInfixExpressionChildren(node, walkingToLeft)
if err != nil {
return "", err
}
var buf bytes.Buffer
buf.WriteString(left)
buf.WriteString("/")
buf.WriteString(right)
buf.WriteString(node.RoundingMethod.String())
return buf.String(), nil
}
// infixNotationsOfInfixExpressionChildren は中置式の左右の子ノードの中置表記を返す。
func infixNotationsOfInfixExpressionChildren(node ast.InfixExpression, walkingToLeft bool) (string, string, error) {
var leftInfixNotation string
var leftErr error
// 演算子が左結合性の場合、左端の単項マイナスは特別扱い
// 例えば、-1+2 の中置表記が (-1)+2 ではなく -1+2 とならなければならない
//
// 左結合性でない場合、例えば (-1)^2 の中置表記は (-1)^2 のままとなる
if node.Left().Type() == ast.UNARY_MINUS_NODE && walkingToLeft && node.IsLeftAssociative() {
leftUMinus := node.Left().(ast.PrefixExpression)
leftInfixNotation, leftErr = infixNotationOfPrefixExpression(leftUMinus, walkingToLeft)
} else {
leftInfixNotation, leftErr = parenthesizeChildOfInfixExpression(
node,
node.Left(),
node.IsLeftAssociative(),
walkingToLeft,
)
}
if leftErr != nil {
return "", "", leftErr
}
rightInfixNotation, rightErr := parenthesizeChildOfInfixExpression(
node,
node.Right(),
node.IsRightAssociative(),
false,
)
if rightErr != nil {
return "", "", rightErr
}
return leftInfixNotation, rightInfixNotation, nil
}
// infixNotationOfRandomNumber はランダム数値取り出しの中置表記を返す。
func infixNotationOfRandomNumber(node ast.InfixExpression) (string, error) {
var out bytes.Buffer
n, err := infixNotationOfInfixExpression(node, true)
if err != nil {
return "", err
}
out.WriteString("[")
out.WriteString(n)
out.WriteString("]")
return out.String(), nil
}
// infixNotationOfSumRollResult は加算ロール結果の中置表記を返す。
func infixNotationOfSumRollResult(node *ast.SumRollResult) (string, error) {
dieValueStrs := []string{}
for _, d := range node.Dice {
dieValueStrs = append(dieValueStrs, fmt.Sprintf("%d", d.Value))
}
return fmt.Sprintf("%d[%s]", node.Value(), strings.Join(dieValueStrs, ",")), nil
}
// FormatModifier は修正値を符号に応じて整形する
func FormatModifier(modifier int) string {
if modifier == 0 {
return ""
}
if modifier > 0 {
return fmt.Sprintf("+%d", modifier)
}
return fmt.Sprintf("%d", modifier)
}