栈的一种Go语言实现
package mainimport ( "errors" "fmt")type Stack struct { MaxTop int //栈的最大容量 Top int //栈顶 arr [5]int}func (s *Stack) Push(val int) (err error) { //判断栈是否已满 if s.Top == s.MaxTop - 1 { fmt.Println("stack full") return errors.New("stack full") } s.Top++ s.arr[s.Top] = val return}func (s *Stack) Pop() (val int, err error) { //判断栈是否为空 if s.Top == -1 { fmt.Println("stack empty") return -1, errors.New("stack empty") } val = s.arr[s.Top] s.Top-- return val, nil}func (s *Stack) List() { //判断栈是否为空 if s.Top == -1 { fmt.Println("stack empty") return } //从栈顶开始遍历 for i := s.Top; i >= 0; i-- { fmt.Printf("arr[%d]=%d\n", i, s.arr[i]) }}func main(){ stack := &Stack{ MaxTop: 5, Top: -1, } //入栈 stack.Push(1) stack.Push(2) stack.Push(3) stack.Push(4) stack.Push(5) stack.Push(6) //显示 stack.List() //弹出 val, _ := stack.Pop() val, _ = stack.Pop() val, _ = stack.Pop() val, _ = stack.Pop() val, _ = stack.Pop() //val, _ = stack.Pop() fmt.Println("出栈val=", val) stack.List()}利用案例：
问题：计算一串字符串表达式
思路：
1.创立两个栈，一个是寄存数字的栈，一个是寄存操作符的栈，记为numStack, operStack；
2.如果扫描字符串时发现是数字，则间接入数栈；
3.如果发现是一个运算符则分为两种状况：
3.1如果操作符栈operStack是一个空栈，则间接入栈；
3.2如果操作符栈operStack不是一个空栈则依照操作符的优先级分为两种状况计算：
3.2.1如果发现operStack栈顶的运算符的优先级大于等于以后筹备入栈的运算符的优先级，就从符号栈pop出操作符，同时从数栈pop出两个数进行运算，将运算后的后果再从新入栈到数栈，再将以后筹备入栈的符号入栈到操作符栈；
3.2.2 否则，运算符间接入栈；
4.如果扫描表达式结束，顺次从符号栈取出符号，而后从数栈取出两个数，将运算后的后果再入栈，直到符号栈为空，此时数栈中的值为表达式的计算结果。
package mainimport ( "errors" "fmt" "strconv")type expStack struct { MaxTop int //栈的最大容量 Top int //栈顶 arr [20]int}func (s *expStack) Push(val int) (err error) { //判断栈是否已满 if s.Top == s.MaxTop - 1 { fmt.Println("stack full") return errors.New("stack full") } s.Top++ s.arr[s.Top] = val return}func (s *expStack) Pop() (val int, err error) { //判断栈是否为空 if s.Top == -1 { fmt.Println("stack empty") return -1, errors.New("stack empty") } val = s.arr[s.Top] s.Top-- return val, nil}func (s *expStack) List() { //判断栈是否为空 if s.Top == -1 { fmt.Println("stack empty") return } //从栈顶开始遍历 for i := s.Top; i >= 0; i-- { fmt.Printf("arr[%d]=%d\n", i, s.arr[i]) }}//判断一个字符是否是运算符func (s *expStack) IsOper(val int) bool { if val == 42 || val == 43 || val == 45 || val == 47 { return true }else { return false }}//运算办法func (s *expStack) Cal(num1, num2, oper int) int { res := 0 switch oper { case 42: res = num2 * num1 case 43: res = num2 + num1 case 45: res = num2 - num1 case 47: res = num2 / num1 default: fmt.Println("运算符谬误") } return res}//返回运算符的优先级，自定义func (s *expStack) Priority(oper int) int { res := 0 if oper == 42 || oper == 47 { res = 1 //自定义 }else if oper == 43 || oper == 45 { res = 0 }else { fmt.Println("其余状况") } return res}func main(){ //数栈 numStack := &expStack{ MaxTop: 20, Top: -1, } //符号栈 operStack := expStack{ MaxTop: 20, Top: -1, } exp := "30+20*6-2" index := 0 num1, num2, oper := 0, 0, 0 keepNum := "" for { //解决多位数问题 ch := exp[index:index+1] //"3" temp := int([]byte(ch)[0]) //字符对应的ASCII码值 if operStack.IsOper(temp) { //是符号 //如果是空栈，间接入栈 if operStack.Top == -1 { operStack.Push(temp) }else { //如果发现operStack栈顶的运算符的优先级大于等于以后筹备入栈的运算符的优先级， //就从符号栈pop出操作符，同时从数栈pop出两个数进行运算，将运算后的后果再从新入栈到数栈， //再将以后筹备入栈的符号入栈到操作符栈； if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(temp){ num1, _ = numStack.Pop() num2, _ = numStack.Pop() oper, _ = operStack.Pop() result := operStack.Cal(num1, num2, oper) //计算结果入栈 numStack.Push(result) //入栈以后符号 operStack.Push(temp) }else{ operStack.Push(temp) } } }else { //阐明是数 //定义一个变量keepNum 做字符串拼接解决多位数 //每次要向index的前面字符测试一下，看看是不是运算法 keepNum += ch if index == len(exp) - 1 { //如果是字符串的最初则间接入栈，避免引起空指针谬误 val, _ := strconv.ParseInt(keepNum, 10, 64) numStack.Push(int(val)) }else { if operStack.IsOper(int([]byte(exp[index+1:index+2])[0])) { //判断下一个字符是不是运算符 val, _ := strconv.ParseInt(keepNum, 10, 64) numStack.Push(int(val)) keepNum = "" } } } //判断index是否到字符串最初 if index + 1 == len(exp) { break } index++ } //如果扫描表达式结束，顺次从符号栈取出符号，而后从数栈取出两个数， //将运算后的后果再入栈，直到符号栈为空，此时数栈中的值为表达式的计算结果。 for { if operStack.Top == -1 { break } num1, _ = numStack.Pop() num2, _ = numStack.Pop() oper, _ = operStack.Pop() result := operStack.Cal(num1, num2, oper) //计算结果入栈 numStack.Push(result) } //如果到这里，则后果就是numStack最初的数 res, _ := numStack.Pop() fmt.Printf("表达式%s = %v", exp, res)}