逆波兰表示法的Golang实现

最近在看程杰写的《大话数据结构》，之前也看过他写的《大话设计模式》，虽然书中好多段子都很“尬”，但是整体风格还是很合我的胃口的。

今天看到第四章，在介绍栈的时候提到了逆波兰表示法，这个算法好像上学的时候在 POJ 上面做过。算法我也好久没碰了，今天用Golang实现一下，就当练练手吧。

代码很简单，我写了比较详细的注释，那就直接看代码吧：

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
	"strconv"
)

type node struct {
	value interface{}
	next  *node
}

// 栈的链式结构实现
type Stack struct {
	top    *node
	length int
}

func NewStack() *Stack {
	return &Stack{nil, 0}
}

func (s *Stack) Len() int {
	return s.length
}

// 获取栈顶元素
func (s *Stack) Peek() interface{} {
	if s.length == 0 {
		return nil
	}
	return s.top.value
}

// 弹出栈顶
func (s *Stack) Pop() interface{} {
	if s.length == 0 {
		return nil
	}
	n := s.top
	s.top = n.next
	s.length--
	return n.value
}

// 压栈
func (s *Stack) Push(value interface{}) {
	n := &node{value, s.top}
	// 从头部插入
	s.top = n
	s.length++
}

func main() {
	var str string
	fmt.Printf("Please enter expression: ")
	scanner := bufio.NewScanner(os.Stdin)
	if scanner.Scan() {
		// 读取表达式
		str = scanner.Text()
	}
	if err := scanner.Err(); err != nil {
		panic(err)
	}
	// 转为字符串数组
	exp := toExp(str)
	fmt.Print("Infix expression: ")
	printExp(exp)
	// 转为后缀表达式
	postfixExp := toPostfix(exp)
	fmt.Print("Postfix expression: ")
	printExp(postfixExp)
	// 计算结果
	value := calValue(postfixExp)
	fmt.Println(fmt.Sprintf("Result: %d", value))
}

// 将数字和操作符转为字符串数组
func toExp(str string) []string {
	s := make([]string, 0)
	var t bytes.Buffer
	n := 0 // 用于判断括号是否成对
	for _, r := range str {
		if r == ' ' {
			// 去掉空格
			continue
		}
		if isDigit(r) {
			// 是数字 就写到缓存中
			t.WriteRune(r)
		} else {
			rs := string(r)
			if !isSign(rs) {
				panic("unknown sign: " + rs)
			}
			if t.Len() > 0 {
				// 遇到符号 把缓存中的数字 输出为数
				// 例如 将缓存中的 ['1', '2', '3'] 输出为 "123"
				s = append(s, t.String())
				t.Reset()
			}
			s = append(s, rs)
			if r == '(' {
				n++
			} else if r == ')' {
				n--
			}
		}
	}
	if t.Len() > 0 {
		// 最后一个操作符后面的数字 如果最后一个操作符是 ")" 那么 t.Len() 为0
		s = append(s, t.String())
	}
	if n != 0 {
		panic("the number of '(' is not equal to the number of ')' ")
	}
	return s
}

func printExp(exp []string) {
	for _, s := range exp {
		fmt.Print(s, " ")
	}
	fmt.Println()
}

// 是否数字
func isDigit(r rune) bool {
	if r >= '0' && r <= '9' {
		return true
	}
	return false
}

// 是否符号
func isSign(s string) bool {
	switch s {
	case "+", "-", "*", "/", "(", ")":
		return true
	default:
		return false
	}
}

// 中缀表达式转后缀表达式
func toPostfix(exp []string) []string {
	result := make([]string, 0)
	s := NewStack()
	for _, str := range exp {
		if isSign(str) {
			// 若是符号
			if str == "(" || s.Len() == 0 {
				// "(" 或者 栈为空 直接进栈
				// 括号中的计算 需要单独处理 相当于一个新的上下文
				// 如果栈为空 需要先进栈 和后续操作符比较优先级之后 才能决定计算顺序
				s.Push(str)
			} else {
				if str == ")" {
					// 若为 ")" 依次弹出栈顶元素并输出 直到遇到 "("
					for s.Len() > 0 {
						if s.Peek().(string) == "(" {
							s.Pop()
							break
						}
						result = appendStr(result, s.Pop().(string))
					}
				} else {
					// 判断其与栈顶符号的优先级
					// 如果栈顶是 "(" 说明是新的上下文 不能相互比较优先级
					for s.Len() > 0 && s.Peek().(string) != "(" && signCompare(str, s.Peek().(string)) <= 0 {
						// 当前符号的优先级 不大于栈顶元素 弹出栈顶元素并输出
						// 优先级高的操作 需要先计算
						// 优先级相同 因为栈中的操作是先放进去的 也需要先计算
						result = appendStr(result, s.Pop().(string))
					}
					// 当前符号入栈
					s.Push(str)
				}
			}
		} else {
			// 若是数字就输出
			result = appendStr(result, str)
		}
	}
	for s.Len() > 0 {
		result = appendStr(result, s.Pop().(string))
	}
	return result
}

func appendStr(slice []string, str string) []string {
	if str == "(" || str == ")" {
		// 后缀表达式 不包含括号
		return slice
	}
	return append(slice, str)
}

// 比较符号优先级
func signCompare(a, b string) int {
	return getSignValue(a) - getSignValue(b)
}

// 优先级越高 值越大
func getSignValue(a string) int {
	switch a {
	case "(", ")":
		return 2
	case "*", "/":
		return 1
	default:
		return 0
	}
}

// 通过后缀表达式 计算值
func calValue(exp []string) int {
	s := NewStack()
	for _, str := range exp {
		if isSign(str) {
			// 如果是符号 弹出栈顶的两个元素 进行计算
			// 因为栈结构先进后出 所以先弹出b
			b := getInt(s)
			a := getInt(s)
			var n int
			switch str {
			case "+":
				n = a + b
			case "-":
				n = a - b
			case "*":
				n = a * b
			case "/":
				n = a / b
			}
			// 计算结果压栈
			s.Push(n)
		} else {
			// 数字直接压栈 也可以在这里做类型转换 使栈中的值均为int
			s.Push(str)
		}
	}
	// 栈顶元素 为最终结果
	return getInt(s)
}

// 弹出栈顶元素 并转为int
func getInt(s *Stack) int {
	v := s.Pop()
	switch v.(type) {
	case int: // push进去的计算结果为int
		return v.(int)
	case string: // exp中的数据为string
		if i, err := strconv.Atoi(v.(string)); err != nil {
			panic(err)
		} else {
			return i
		}
	}
	panic(fmt.Sprintf("unknown value type: %T", v))
}

运行结果：

Please enter expression: 9+(3-1)*3+10/2
Infix expression: 9 + ( 3 - 1 ) * 3 + 10 / 2 
Postfix expression: 9 3 1 - 3 * + 10 2 / + 
Result: 20

总结

逆波兰表示法解决了计算机不容易处理中缀表达式的问题。之前策划提出过能否在技能配置表中，使用字符串来配置每个技能的伤害计算公式，以方便更好的定制技能效果。这个需求其实就可以使用逆波兰表示法解决。不过后来被我以性能较差为由给拒绝了。看一下benchmark吧，这只是一个简单的例子，如果真的应用在技能系统里，还需要动态解析玩家属性等操作，差距会更大一些。

package main

import (
	"testing"
)

var exp []string

func init() {
	str := "1+(2*3+4-5*6/2+7)-2"
	exp = toExp(str)
}

func BenchmarkRPN(b *testing.B) {
	var n int
	for i := 0; i < b.N; i++ {
		n = calValue(toPostfix(exp))
	}
	b.Log(n)
}

func BenchmarkDirect(b *testing.B) {
	var n int
	for i := 0; i < b.N; i++ {
		n = 1 + (2*3 + 4 - 5*6/2 + 7) - 2
	}
	b.Log(n)
}

运行结果：

500000	      2787 ns/op
--- BENCH: BenchmarkRPN-8
	main_test.go:19: 1
	main_test.go:19: 1
	main_test.go:19: 1
	main_test.go:19: 1
2000000000	         0.29 ns/op
--- BENCH: BenchmarkDirect-8
	main_test.go:27: 1
	main_test.go:27: 1
	main_test.go:27: 1
	main_test.go:27: 1
	main_test.go:27: 1
	main_test.go:27: 1