// 第 7 周 – 中缀 -> 后缀转换（简化的调度场算法）
// 运行：go run ./w07/infixtopostfix
package main

import (
	"fmt"
	"strings"
	"unicode"
)

func precedence(op rune) int {
	switch op {
	case '*', '/':
		return 2
	case '+', '-':
		return 1
	}
	return 0
}

func convert(infix string) string {
	var out []string
	var ops []rune // 栈
	for _, c := range infix {
		switch {
		case c == ' ':
		case unicode.IsLetter(c) || unicode.IsDigit(c):
			out = append(out, string(c))
		case c == '(':
			ops = append(ops, c)
		case c == ')':
			for ops[len(ops)-1] != '(' {
				out = append(out, string(ops[len(ops)-1]))
				ops = ops[:len(ops)-1]
			}
			ops = ops[:len(ops)-1] // 丢弃 '('
		default:
			for len(ops) > 0 && precedence(ops[len(ops)-1]) >= precedence(c) {
				out = append(out, string(ops[len(ops)-1]))
				ops = ops[:len(ops)-1]
			}
			ops = append(ops, c)
		}
	}
	for len(ops) > 0 {
		out = append(out, string(ops[len(ops)-1]))
		ops = ops[:len(ops)-1]
	}
	return strings.Join(out, " ")
}

func main() {
	for _, t := range []string{"3 + 4 * 2", "(3 + 4) * 2", "a + b * c - d", "(a + b) * (c - d)", "1 + 2 - 3 * 4 / 5"} {
		fmt.Printf("%-20s ->  %s\n", t, convert(t))
	}
}