// 第 14 周 – 表达式树：用栈由后缀形式构造，用递归求值
// 运行：go run ./w14/expressiontree
package main

import (
	"fmt"
	"strconv"
	"strings"
)

type Node struct {
	Token       string
	Left, Right *Node
}

func isOp(t string) bool { return len(t) == 1 && strings.Contains("+-*/", t) }

func fromPostfix(expr string) *Node {
	var st []*Node
	for _, t := range strings.Fields(expr) {
		if isOp(t) {
			r, l := st[len(st)-1], st[len(st)-2]
			st = st[:len(st)-2]
			st = append(st, &Node{t, l, r})
		} else {
			st = append(st, &Node{Token: t})
		}
	}
	return st[0]
}

func eval(p *Node) float64 {
	if !isOp(p.Token) {
		v, _ := strconv.ParseFloat(p.Token, 64)
		return v
	}
	a, b := eval(p.Left), eval(p.Right)
	switch p.Token {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	}
	return a / b
}

func infix(p *Node) string {
	if !isOp(p.Token) {
		return p.Token
	}
	return "(" + infix(p.Left) + " " + p.Token + " " + infix(p.Right) + ")"
}

func prefix(p *Node) string {
	if !isOp(p.Token) {
		return p.Token
	}
	return p.Token + " " + prefix(p.Left) + " " + prefix(p.Right)
}

func main() {
	t := fromPostfix("3 4 + 5 2 - *")
	fmt.Println("infix: ", infix(t))
	fmt.Println("prefix:", prefix(t))
	fmt.Println("value: ", eval(t))
}