中缀表达式转后缀表达式

2018-07-19 | 阅读：次

最近参加了一次电话面试，对方出的题目是把一个中缀表达式转换为后缀表达式,这里对问题做了一些简化，操作符只有+-*/和左右括号。惭愧的是因为之前数据结构和算法的基础不牢，在几十分钟的时间内都没搞明白后缀表达式是如何去计算的，更不要谈如何去做转换了。结束之后自己先搜索了下后缀表达式。知道含义了之后，就能开始去思考如何去完成这个转换了。正好在csdn上看到了一篇文章，将整个中缀表达式转换为一个二叉树，树的枝干节点是操作符，叶子节点都是数字，这样一来整个模型就清晰了。从这棵树就能直接很轻松的生成前缀、中缀或者后缀表达式了。

正好最近在学习用go，简单写了一般。构造树的过程很粗暴，时间上应该是可以优化的，完整代码如下：

package main

import (
	"fmt"
)

type Node struct {
	opt    string
	leaf   bool
	num    string
	left   *Node
	right  *Node
	parent *Node
}

func getExp(expr string, parent *Node) Node {
	if len(expr) == 1 {
		return Node{
			parent: parent,
			leaf:   true,
			num:    expr,
		}
	}

	curLvl := 0
	topLvl := 0
	topOptIdx := 0
	var lastOpt byte = 0

	for i := 0; i < len(expr); i++ {
		if expr[i] == '(' {
			curLvl += 1
		} else if expr[i] == ')' {
			curLvl -= 1
		} else if expr[i] == '*' || expr[i] == '/' {
			if curLvl < topLvl || lastOpt == 0 {
				topLvl = curLvl
				topOptIdx = i
				lastOpt = expr[i]
			}
		} else if expr[i] == '+' || expr[i] == '-' {
			if curLvl <= topLvl || lastOpt == 0 {
				topLvl = curLvl
				topOptIdx = i
				lastOpt = expr[i]
			}
			if curLvl == 0 {
				break
			}
		}
	}

	//fmt.Print(expr, "\t", topOptIdx, "\n")
	node := Node{
		opt:    string(expr[topOptIdx]),
		parent: parent,
	}
	left := getExp(expr[topLvl:topOptIdx], &node)
	node.left = &left
	right := getExp(expr[topOptIdx+1:len(expr)-topLvl], &node)
	node.right = &right
	return node
}

func printExpr(node *Node) string {
	if node.leaf {
		return node.num
	}

	return printExpr(node.left) + printExpr(node.right) + node.opt
}

func main() {
	expr := "(1+(3+2))*(1-5)"
	//expr := "(3+2)*1"
	nilTop := Node{}
	root := getExp(expr, &nilTop)
	ret := printExpr(root.left) + printExpr(root.right) + root.opt
	fmt.Print(ret)
}

BTW, wiki中同样提到了另外一种调度场算法,具体算法的计算过程参见wiki描述，估计正常的话在面试时间内如果不清楚后缀表达式是啥(比如我自己……)完整想出这个算法的话会比较困难……当时确实在这个方向思考，但是没有想清楚后缀表达式的计算过程以及如何处理嵌套和运算符优先级。同样，把这个算法用golang实现一版如下：

package main

import (
	list2 "container/list"
	"fmt"
)

func main() {
	expr := "(1-4)*5+(3+2)*(1-5)+1*3"
	optList := list2.New()
	output := list2.New()
	for i := 0; i < len(expr); i++ {
		//fmt.Print(string(expr[i]), "\n")
		switch expr[i] {
		case '+':
			fallthrough
		case '-':
			for optList.Front() != nil {
				t, _ := optList.Front().Value.(uint8)
				if t == '(' {
					break
				}
				output.PushBack(t)
				optList.Remove(optList.Front())
			}
			optList.PushFront(expr[i])

		case '*':
			fallthrough
		case '/':
			for optList.Front() != nil {
				t, _ := optList.Front().Value.(uint8)
				if t == '*' || t == '/' {
					output.PushBack(t)
					optList.Remove(optList.Front())
				} else {
					break
				}
			}
			optList.PushFront(expr[i])

		case ')':
			for optList.Front() != nil {
				t, _ := optList.Front().Value.(uint8)
				if t == '(' {
					optList.Remove(optList.Front())
					continue
				}
				output.PushBack(t)
				optList.Remove(optList.Front())
			}
		case '(':
			optList.PushFront(expr[i])
		default:
			output.PushBack(expr[i])
		}

		//fmt.Print("output:\n")
		//for ele := output.Front(); ele != nil; ele = ele.Next() {
		//	str, ok := ele.Value.(uint8)
		//	if ok {
		//		fmt.Print(string(str))
		//	} else {
		//		fmt.Print(" bad ")
		//	}
		//}
		//fmt.Print("\n")

	}

	for ele := optList.Front(); ele != nil; ele = ele.Next() {
		output.PushBack(ele.Value)
	}
	fmt.Print("output:\n")
	for ele := output.Front(); ele != nil; ele = ele.Next() {
		str, ok := ele.Value.(uint8)
		if ok {
			fmt.Print(string(str))
		} else {
			fmt.Print(" bad ")
		}
	}
	fmt.Print("\n")
}

在这中间逐渐了解到了很多golang自己比较独特的东西，比如：

switch中的每个case默认会break，反而是需要直落的需要显示的标明fallthrough,这样确实更合理，应该能拯救一堆的奇异bug
if 语句后面必须接一对花括号，嗯~ o(￣▽￣)o 是个好习惯
go的container/list容器，我理解为类似java中的List。list中定义了一个element结构体，其中内部定义了Value保存具体元素。Value是一个空的interface，因此list中可以保存任何对象。val, ok := optList.Front().Value.(uint8) 通过.(uint8)的方式做类型转换，通过ok判断转换是否成功。感觉有些繁琐，还是喜欢python中的str()\int() 函数

rockiee

rockiee's stone

中缀表达式转后缀表达式

目录