关于数据结构:数据结构栈

栈的一种 Go 语言实现

package main

import (
    "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 main

import (
    "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)
}