определение
Стек — это специальный линейный список, который может выполнять операции вставки или удаления только на одном конце, а конец, который может выполнять операции, называется стеком.вершина стека, другой конец называетсянижняя часть стека. Также благодаря этой особенностиЭлементы, которые входят первыми, могут выйти только последними, поэтому стекпоследний пришел первый вышеллинейный стол.
Стек представляет собой линейный список, поэтому его хранение может быть связанным хранилищем или последовательным хранилищем. Цепной стек хранения, называемыйцепной стек, последовательно сохраняемый стек, называемыйпоследовательный стек. В следующем примере срез массива переменных языка go используется для завершения хранения стека, поэтому он сохраняется последовательно.
описание стека
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++
}
поп
Выньте верхний элемент стека и опустите вершину стека на единицу, если стек пуст, будет сообщено об ошибке
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
}
Получить верхний элемент стека
Получить значение верхнего элемента, но не стека
func (s *Stack) GetTop() data{
if s.top == -1 {
return nil
}
return s.list[s.top]
}
}
Применение: вычисление арифметического выражения
постфиксное выражение
Арифметические выражения, используемые в нашей повседневной жизни, например: 5+6/2-3*4, состоят из двух типов объектов:
- Операнды, такие как: 5, 6, 2 и т.д.
- Символы операций, такие как +, - и т. д., и разные операторы имеют разный приоритет
так какСимволы операторов имеют разный приоритет, а символы операторов находятся в операндах., что усложняет операцию. Как понять это? Возьмем приведенное выше выражение в качестве примера, когда программа переходит к знаку +, должна быть выполнена операция +, так что это 5 + 6? Очевидно, что нет, потому что после 6 стоит оператор /, а приоритет / выше, чем +, поэтому 6 является операндом /, а не операндом +. А как насчет наоборот?При обходе символа операции вы уже знаете два соответствующих операнда., что упрощает оценку. Это придумали великие ученыепостфиксное выражение, также известный как обратный польский, относится кбез скобок, оператор ставится после двух операндов, а все вычисления выполняются в том порядке, в котором стоят операторы, строго слева направо (правила старшинства операторов больше не учитываются).
- Инфиксные выражения: 2 + 9 / 3 - 5
- Постфиксное выражение: 2 9 3 / + 5 -
Конечно, оба выражения выражают один и тот же смысл.
Оценка постфиксного выражения
Поскольку в постфиксных выражениях не нужно учитывать правила приоритета операторов, алгоритм вычисления становится простым:
1. Перебрать выражения слева направо;
2. Когда встречается число, оно сразу помещается в стек;
3. При встрече с оператором всплывают два элемента.Первый извлеченный элемент помещается справа от оператора, а последний элемент помещается слева от оператора.Затем результат помещается в стек. ;
4. До тех пор, пока не будет пройдено все выражение, верхний элемент стека, который окончательно выталкивается, является окончательным значением выражения.
Взяв в качестве примера выражение 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 -
можно увидеть,Относительное положение чисел не меняется, но меняется положение символов., то в процессе конвертации нам нужно сравнить приоритеты различных символов операций, а затем сначала вывести операторы с более высоким приоритетом, а потом с более низкими, чтобы можно было сохранить порядок вычисления при вычислении суффиксного выражения , не быть измененным. (Левая и правая круглые скобки также считаются рабочими символами.) Конкретные шаги алгоритма следующие:
1. Перебрать инфиксное выражение слева направо;
2. Если это операнд, вывести его напрямую;
3. Если это символ оператора: еслиОператоры с приоритетом выше вершины стека(стек не пуст), то запихиваем в стек символ операции, т.к. если приоритет символа операции больше, чем у вершины стека, значит, его нужно сначала вычислить, а потом вводить позже, поэтому в последующей операции он должен выйти перед символом наверху стека, поэтому при оценке суффикса он должен быть рассчитан первым;
4. Если это символ оператора: еслиСимволы операций с приоритетом меньше или равным вершине стека(стек не пуст), символ операции наверху стекапоп и вывод, а затем продолжить сравнение со следующим новым элементом вершины стека, пока приоритет не станет больше, чем у нового элемента вершины стека, поместите символ операции в стек;
5. Левые круглые скобки: выражения в круглых скобках должны быть вычислены в первую очередь, поэтому при сканировании левых круглых скобок левые круглые скобки помещаются непосредственно в стек, иЛевая скобка в стеке имеет самый низкий приоритет. Поскольку операторы в скобках оцениваются первыми;
6. Правая скобка: поставить верхний элемент стекапоп и войти, пока не встретится открывающая скобка (выскакивает, но не выводится);
7. После обхода всего выражения элементы в стеке извлекаются один за другим и выводятся.
Возьмем для примера 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!