栈 - 积至（极致）

Anonymous 收录于 Go

2023-09-19 约 700 字预计阅读 3 分钟

栈

栈的定义

栈是一个先入后出的有序列表
栈是限制线性表中的元素的插入和删除，只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端，称为栈顶，另一端称为栈底。

运用场景

子程序的调用，在调往子程序前，会先将下一个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
处理递归调用
表达式的转换（中缀表达式转后缀表达式）与求值。
二叉树的遍历
图的深度优先（depth-first）搜索法。

代码实现栈

通过数组来模拟
定义栈顶变量top,初始化为-1
入栈：
- top++
- element[top] = data
出栈：
- object = element[top]
- element[top] = null
- top–

package stack

import "fmt"

type ArrayStack struct {
	// 切片
	Element []interface{}
	// 栈顶指针
	Top int64
	// 栈大小
	MaxSize int64
}

// NewArrayStack 构造函数
func NewArrayStack(size int64) *ArrayStack {
	return &ArrayStack{
		Element: make([]interface{}, size),
		Top:     -1,
		MaxSize: size,
	}
}

func (s *ArrayStack) IsFull() bool {
	if s.Top == s.MaxSize-1 {
		return true
	} else {
		return false
	}
}

func (s *ArrayStack) IsEmpty() bool {
	if s.Top == -1 {
		return true
	} else {
		return false
	}
}

func (s *ArrayStack) Pop() interface{} {
	if s.IsEmpty() {
		fmt.Println("栈中没有元素")
		return nil
	} else {
		ele := s.Element[s.Top]
		s.Element[s.Top] = nil
		s.Top--
		return ele
	}
}

func (s *ArrayStack) Push(ele interface{}) {
	if s.IsFull() {
		fmt.Println("栈已满。。。")
		return
	} else {
		s.Top++
		s.Element[s.Top] = ele
	}
}

func (s *ArrayStack) List() {
	if s.IsEmpty() {
		fmt.Println("栈为空")
	}
	for {
		if s.Top == -1 {
			break
		}
		pop := s.Pop()
		fmt.Println("元素：", pop)
	}
}

// Peek 查看栈顶元素
func (s *ArrayStack) Peek() interface{} {
	if s.IsEmpty() {
		fmt.Println("栈为空")
		return nil
	}
	ele := s.Element[s.Top]
	return ele
}

栈的运用

使用栈完成表达式的计算

通过一个index值来遍历表达式
如果是数字，就入数栈
如果是符号分情况
1. 如果当前栈为空，直接入符号栈
2. 如果符号栈有数据，需要比较，如果当前操作符的优先级小于或等于栈中的操作符，就需要从数栈中pop出两个数，从符号栈中pop出一个符号，进行运算将得到的结果放入数栈中，将当前的操作符放入符号栈中，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行。
最后在数栈中只有一个数时，表示运算结束。

中缀表达式转后缀表达式

初始化两个栈：运算符栈s1和存储中间结果的栈s2；
从左到右扫描中缀表达式
遇到操作数时将其压入s2中
遇到运算符时比较其与s1栈顶运算符的优先级
1. 如果s1为空，或栈顶运算符为左括号，则直接将次运算符压入s1中
2. 如果运算符优先级比栈顶运算符的高，也将其压入s1中
3. 如果运算符优先级比栈顶运算符的低，将s1的栈顶运算符弹出并压入s2中，再次进行（4.1）的操作与s1中新的栈顶元素比较；
遇到括号时：
1. 如果是左括号，直接压入s1中
2. 如果是右括号，则依次弹出s1栈顶的运算符，并压入s2中，直到遇见左括号为止，此时将这一对括号丢弃
重复2-5的步骤直到表达式的最右边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素，将结果逆序后即为后缀表达式

代码实现

package main

import (
	"fmt"
	"my-practice/5.stack/stack"
	"regexp"
)

func main() {

	fmt.Println("请输入表达式：")

	// 接收表达式
	var expression string
	fmt.Scanln(&expression)
	// 遍历切片中的字符
	expressionList := toInfixExpressionList(expression)
	fmt.Println("中缀表达式：", expressionList)

	suffixExpression := parseSuffixExpression(expressionList)
	fmt.Println("后缀表达式：", suffixExpression)

}

// 中缀表达式转 string list : eg 12.34-(4+8)*5
func toInfixExpressionList(s string) []string {
	// 定义一个 切片
	var charSlice = make([]string, len(s))
	// expression := "1+2-5+5*6"
	var numStr string
	index := 0

	runes := []rune(s)

	for i := 0; i < len(runes); {
		if runes[i] < 48 || runes[i] > 57 {
			charSlice[index] = string(runes[i])
			index++
			i++
		} else {
			numStr = ""
			// 拼接数字
			for i < len(runes) && ((runes[i] >= 48 && runes[i] <= 57) || 46 == runes[i]) {
				numStr += string(runes[i])
				i++
			}
			charSlice[index] = numStr
			index++
		}
	}
	return charSlice
}

// 中缀表达式转后缀表达式
func parseSuffixExpression(strSlice []string) []string {
	// 定义一个符号栈
	var operatorStack = stack.NewArrayStack(64) //创建栈

	// 定义一个中间数组
	var middleList = make([]string, 4)

	// 遍历 strSlice 切片
	for _, char := range strSlice {
		// 如果是一个数，就加入 middleList，通过正则表达式来匹配
		reg, _ := regexp.Compile("\\d+")
		if reg.Match([]byte(char)) {
			middleList = append(middleList, char)
		} else if "(" == char { // 如果是左括号直接入栈
			operatorStack.Push(char)
		} else if ")" == char { // 如果是右括号，则依次弹出s1栈顶的运算符，并压入s2中，直到遇见左括号为止，此时将这一对括号丢弃
			for operatorStack.Peek() != "(" {
				middleList = append(middleList, fmt.Sprintf("%s", operatorStack.Pop()))
			}
			operatorStack.Pop() // 消除小括号
		} else { // 考虑运算符的优先级问题
			// 当char的优先级小于等于栈顶的运算符的优先级时
			for !operatorStack.IsEmpty() && operationLevel(char) <= operationLevel(fmt.Sprintf("%s", operatorStack.Peek())) {
				// 判断优先级
				middleList = append(middleList, fmt.Sprintf("%s", operatorStack.Pop()))
			}
			operatorStack.Push(char)
		}
	}

	// 将运算符栈中剩余的元素加入 middleList 中
	for !operatorStack.IsEmpty() {
		middleList = append(middleList, fmt.Sprintf("%s", operatorStack.Pop()))
	}

	return middleList
}

// 判断运算符的优先级
func operationLevel(char string) int {
	switch char {
	case "+":
		return 1
	case "-":
		return 1
	case "*":
		return 2
	case "/":
		return 2
	default:
		return 0
	}
}

实际运用-逆波兰计算器

在上面的方法中已经计算出了逆波兰表达式（逆序输出后缀表达式）通过遍历切片计算即可

func calculate(slice []string) interface{} {
	// 创建一个栈
	stack := stack.NewArrayStack(64)
	// 循环遍历后缀表达式
	for _, str := range slice {
		if "" == str {
			continue
		}
		// 使用正则表达式来匹配数字
		reg, _ := regexp.Compile("\\d+")
		// 如果是数字先入栈
		if reg.Match([]byte(str)) {
			stack.Push(str)
		} else {
			// 否则弹出两个数，并运算再入栈
			num1, _ := strconv.ParseFloat(fmt.Sprintf("%s", stack.Pop()), 64)

			num2, _ := strconv.ParseFloat(fmt.Sprintf("%s", stack.Pop()), 64)
			var res float64 = 0.0
			switch str {
			case "+":
				res = num1 + num2
			case "-":
				res = num2 - num1
			case "*":
				res = num2 * num1
			case "/":
				res = num2 / num1
			default:
				fmt.Println("异常的计算符")
				continue
			}
			// 将结果压入栈中,有个坑，这个地方的值是float类型
			stack.Push(fmt.Sprintf("%f", res))
		}
	}
	return stack.Pop()
}

在main中添加代码：

fmt.Println("计算结果：", calculate(suffixExpression))

测试结果

输入：12.34-(4+8)*5

中缀表达式： [12.34 - ( 4 + 8 ) * 5    ]
后缀表达式： [12.34 4 8 + 5 * - ]
计算结果： -47.660000