数据结构之栈——算术表达式求值
定义
栈是一种特殊的线性表，它只能在一端进行插入或者删除操做，能进行操做的一端称为栈顶，另外一端则称为栈底。也因为这个特性，致使先进入的元素，只能后出，所以栈是后进先出的线性表。git
栈是一种线性表，所以它的存储能够是链式存储，也能够是顺序存储。链式存储的栈，称为链栈，顺序存储的栈，称为顺序栈。而下面实例中，使用go语言的可变数组slice完成栈的存储，所以是顺序存储。算法
栈的描述数组
type data interface {}
type Stack struct {
top int // 栈顶，表明栈顶的下标，-1为空栈
list []data // 从0开始存储
}
func New() *Stack{
s := &Stack{top:-1,list: []data{}}
return s
}
复制代码
主要操做
入栈
在栈顶插入一个新元素，称为入栈，首先要判断栈是否已满，满就报错，不然就插入，并将栈顶上升一位。数据结构
// 因为使用的是可变数组，所以不会出现栈满的状况，因此如下代码不须要判断是否栈满，若是是不可变数组，或者是限制容量的栈，则要判断栈是否已满
func (s *Stack) Push (value data) {
s.list = append(s.list,value)
s.top++
}
复制代码
出栈
取出栈顶元素，并将栈顶降低一位，若是栈为空，则报错app
func (s *Stack) Pop() (data,error) {
if s.top == -1 {
return nil,errors.New("栈空")
}
data := s.list[s.top]
s.list = s.list[:s.top]
s.top--
return data,nil
}
复制代码
判空
判断是否为空栈函数
func (s *Stack) IsEmpty() bool{
return s.top == -1
}
复制代码
获取栈顶元素
获得栈顶元素的值，但不出栈post
func (s *Stack) GetTop() data{
if s.top == -1 {
return nil
}
return s.list[s.top]
}
}
复制代码
应用：算术表达式求值
后缀表达式
咱们平常生活中使用的算术表达式，例如：5+6/2-3*4，它由两类对象构成：ui
- 运算数，如：5，6，2等
- 运算符号，如+，-等，并且不一样运算符号优先级不同
因为运算符号优先级不一样，并且运算符号位于运算数中，因此使得运算变得复杂了。 怎么理解呢？拿上面的表达式为例，当程序遍历到+号的时候，要作+运算，那么是5+6吗？很显然不是，由于6后面还有一个/运算符，并且/的优先级大于+，因此6是/的运算数，而不是+的运算数。那么反过来呢？当遍历到一个运算符号的时候，就已经知道对应的两个运算数，这样求值就变的简单了。伟大的科学家们，就此发明了后缀表达式，也称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，全部的计算按运算符出现的顺序，严格从左向右进行（再也不考虑运算符的优先规则）。spa
- 中缀表达式：2 + 9 / 3 - 5
- 后缀表达式：2 9 3 / + 5 -
固然两个表达式，都是表达同一个意思。code
后缀表达式求值
因为后缀表达式不须要考虑运算符的优先规则，所以求值算法就变得简单了：
一、从左到右依次遍历表达式；
二、遇到数字就直接入栈；
三、遇到操做符就弹出两个元素，先弹出的元素放到操做符的右边，后弹出的元素放到操做符的左边（左边的运算数先入栈，所以后出），将计算获得的结果再压入栈；
四、直到整个表达式遍历完，最后弹出的栈顶元素就是表达式最终的值。
以33-5+表达式为例，运行状态以下
func getPostfixExpressionResult(s string) int {
stack := Stack.New()
for _, value := range s {
if unicode.IsDigit(value) {
intValue, _ := strconv.Atoi(string(value))
stack.Push(intValue)
} else {
right, _ := stack.Pop()
left, _ := stack.Pop()
result := calculate(left.(int), right.(int), string(value)) // 封装的 + - * / 求值方法
stack.Push(result)
}
}
result, _ := stack.Pop()
return result.(int)
}
getPostfixExpressionResult("33-5+") // 5
复制代码
能够看得出算法时间复杂度为O(n)，而且经过出栈入栈的形式就能够完成求值过程。
中缀表达式转后缀表达式
接下来看看中缀怎么转后缀，咱们先对比一下两个表达式：
- 中缀表达式：2 + 9 / 3 - 5
- 后缀表达式：2 9 3 / + 5 -
能够看的出来，数字的相对位置是不变的，改变的是符号的位置，那么在转换的过程，咱们须要对比各类运算符号的优先级，而后将优先级高的运算符，先输出，低的后输出，这样在后缀表达式求值的时候，就能保存计算顺序不被改变。（左括号和右括号也当作运算符号）具体的算法步骤以下：
一、从左到右遍历中缀表达式；
二、若是是运算数，直接输出；
三、若是是运算符号：若优先级大于栈顶的运算符号（栈不为空），则将该运算符号压入栈中，由于若是该运算符号优先级比栈顶的大，说明要先被计算，那么它是后入的，所以在以后的操做中，必定比栈顶的符号先出，所以在后缀求值中，确定先被计算；
四、若是是运算符号：若优先级小于等于栈顶的运算符号（栈不为空），则将栈顶的运算符号弹出并输出，而后继续和下一个新的栈顶元素对比，直到优先级大于新的栈顶元素，就将该运算符号压入栈中；
五、左括号：括号里的表达式确定是要先计算的，所以当扫描到左括号的时候，直接将左括号压入栈中，而入了栈里的左括号，优先级就变到最低了。由于括号里的运算符要先运算；
六、右括号：将栈顶元素弹出并输入，直到遇到左括号（弹出，但不输出）；
七、整个表达式遍历完以后，则将栈里的元素一一弹出并输出。
咱们以2*(9+6/3-2)+4为例：
// 利用hash的形式来判断运算符号的优先级
// 有兴趣能够看看百度百科里（后缀表达式）是怎么判断运算符号优先级的，颇有意思 (>▽<)
var opPriority = map[string]int{
"*":2,
"/":2,
"+":1,
"-":1,
"(":0,
}
func infixToPostfix(s string) string{
postfix := ""
stack := Stack.New()
for _,value :=range s{
if unicode.IsDigit(value) {
postfix += string(value)
} else {
op := string(value)
switch op{
case "+","-","*","/":
if stack.IsEmpty(){
stack.Push(op)
} else {
pop := stack.GetTop()
for opPriority[op] <= opPriority[pop.(string)] {
pop,_ = stack.Pop()
postfix += pop.(string)
if stack.IsEmpty() {
break
}
pop = stack.GetTop()
}
stack.Push(op)
}
case "(":
stack.Push(op)
case ")":
for !stack.IsEmpty() {
op,_ := stack.Pop()
if op.(string) == "(" {
break
}
postfix +=op.(string)
}
}
}
}
for !stack.IsEmpty(){
op,_ := stack.Pop()
postfix +=op.(string)
}
return postfix
}
infixToPostfix("2*(9+6/3-5)+4") // 2963/+5-*4+
复制代码
总结
栈是一种被普遍应用的数据结构，除了刚刚举例的算术表达式求值以外，栈还用于函数调用及递归实现，回溯算法等等。在适当的时候选择栈，能够更加高效的解决问题。
ps：在上面的例子里，后缀表达式求值的程序，是一个不太正确的程序，准确的讲，它会把每一个数字当作运算数，即122*，它不会计算出24，而是变成了4，估计你们也猜到缘由了，由于程序是一个字符一个字符的遍历，而没有位数的划分，修正的话，能够用数组来存表达式，这样就能够正确的划分运算数。
Thanks!