Data structure — stack

Stack of a Go language implementation

package main

import (
	"errors"
	"fmt"
)

type Stack struct {
	MaxTop int // Maximum stack size
	Top int / / stack
	arr [5]int
}

func (s *Stack) Push(val int) (err error) {
	// Check whether the stack is full
	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(a) (val int, err error) {
	// Check whether the stack is empty
	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(a) {
	// Check whether the stack is empty
	if s.Top == - 1 {
		fmt.Println("stack empty")
		return
	}

	// Start traversing from the top of the stack
	for i := s.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, s.arr[i])
	}
}

func main(a){
	stack := &Stack{
		MaxTop: 5,
		Top:    - 1,}/ / into the stack
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	stack.Push(4)
	stack.Push(5)
	stack.Push(6)

	/ / show
	stack.List()

	/ / the pop-up
	val, _ := stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	//val, _ = stack.Pop()
	fmt.Println("Out of the stack val =", val)
	stack.List()
}
Copy the code

Application Cases:

Problem: Evaluates a string expression

Ideas:

1. Create two stacks, one is to store numbers, one is to store operators, called numStack, operStack;

2. If the string is a number, it is directly added to the number stack.

3. If it is found to be an operator, there are two cases:

3.1 If operStack is an empty stack, it is directly pushed;

3.2 If operStack is not an empty stack, it is calculated in two cases according to the precedence of the operator:

3.2.1 If the priority of the operator at the top of the operStack is greater than or equal to that of the operator to be pushed, the operator is popped out of the symbol stack and two numbers are popped out of the number stack at the same time. The result of the operation is pushed back onto the number stack, and the symbol to be pushed back onto the operator stack.

3.2.2 Otherwise, the operator is directly pushed;

4. If the expression scanning is completed, take symbols out of the symbol stack, and then take two numbers out of the number stack, and push the calculated results onto the stack until the symbol stack is empty. At this time, the value in the number stack is the calculation result of the expression.

package main

import (
	"errors"
	"fmt"
	"strconv"
)

type expStack struct {
	MaxTop int // Maximum stack size
	Top int / / stack
	arr [20]int
}

func (s *expStack) Push(val int) (err error) {
	// Check whether the stack is full
	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(a) (val int, err error) {
	// Check whether the stack is empty
	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(a) {
	// Check whether the stack is empty
	if s.Top == - 1 {
		fmt.Println("stack empty")
		return
	}

	// Start traversing from the top of the stack
	for i := s.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, s.arr[i])
	}
}

// Determine if a character is an operator
func (s *expStack) IsOper(val int) bool {
	if val == 42 || val == 43 || val == 45 || val == 47 {
		return true
	}else {
		return false}}// Operation method
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("Operator error")}return res
}

// Returns the priority of the operator, custom
func (s *expStack) Priority(oper int) int {
	res := 0
	if oper == 42 || oper == 47 {
		res = 1 / / custom
	}else if oper == 43 || oper == 45 {
		res = 0
	}else {
		fmt.Println("Other circumstances")}return res
}

func main(a){
	/ / number of stack
	numStack := &expStack{
		MaxTop: 20,
		Top:    - 1,}/ / symbol stack
	operStack := expStack{
		MaxTop: 20,
		Top:    - 1,
	}

	exp := "30 + 20 * 6-2"
	index := 0
	num1, num2, oper := 0.0.0
	keepNum := ""

	for {
		// Handle multi-digit problems

		ch := exp[index:index+1] / / "3"
		temp := int([]byte(ch)[0]) // The ASCII code value corresponding to the character
		if operStack.IsOper(temp) { / / is symbolic
			// If the stack is empty, push it directly
			if operStack.Top == - 1 {
				operStack.Push(temp)
			}else {
				// If the priority of the operator at the top of the operStack is greater than or equal to that of the operator being pushed,
				// Pop two numbers from the symbol stack at the same time, and then push the result of the operation back to the number stack.
				// Push the current symbol onto the operator stack;
				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)
					// The calculation result is pushed into the stack
					numStack.Push(result)
					// push the current symbol
					operStack.Push(temp)
				}else{
					operStack.Push(temp)
				}
			}

		}else { // The description is a number
			// Define a variable keepNum to concatenate strings with multiple digits
			// Test each character after index to see if it is an operator
			keepNum += ch

			if index == len(exp) - 1 { // If it is the end of the string, it is pushed directly to prevent null pointer errors
				val, _ := strconv.ParseInt(keepNum, 10.64)
				numStack.Push(int(val))
			}else {
				if operStack.IsOper(int([]byte(exp[index+1:index+2[])0]) {// Determine if the next character is an operator
					val, _ := strconv.ParseInt(keepNum, 10.64)
					numStack.Push(int(val))
					keepNum = ""}}}// Determine if index is at the end of the string
		if index + 1= =len(exp) {
			break
		}
		index++
	}

	// If the expression is scanned, take symbols from the symbol stack, and then two numbers from the number stack,
	// Pushes the result of the operation onto the stack until the symbol stack is empty, at which point the value in the stack is the result of the calculation of the expression.
	for {
		if operStack.Top == - 1 {
			break
		}
		num1, _ = numStack.Pop()
		num2, _ = numStack.Pop()
		oper, _ = operStack.Pop()
		result := operStack.Cal(num1, num2, oper)
		// The calculation result is pushed into the stack
		numStack.Push(result)
	}

	// The result is the last numStack number
	res, _ := numStack.Pop()
	fmt.Printf("Expression %s = %v", exp, res)
}
Copy the code