算术表达式

package main

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

// 栈
type ArrayStack struct {
	// 栈的大小
	maxStack int
	// 模拟栈
	stack []interface{}
	// 当前栈所在的位置
	top int
}

func NewStack(maxStack int) *ArrayStack {
	return &ArrayStack{
		maxStack: maxStack,
		stack:    make([]interface{}, maxStack),
		top:      -1,
	}
}

/*
1. 压栈
2. 弹栈
3. 判断是否是空栈
4. 判断是否是满栈
5. 查看栈顶数据
6. 打印栈列表
*/

// 是否为满栈
func (as *ArrayStack) IsFull() bool {
	return as.top == as.maxStack-1
}

// 是否为空栈
func (as *ArrayStack) IsEmpty() bool {
	return as.top == -1
}

// 弹栈
func (as *ArrayStack) Pop() (interface{}, error) {

	if as.IsEmpty() {
		fmt.Println("该栈为空")
		return nil, errors.New("该栈为空")
	}
	value := as.stack[as.top]
	as.top--
	return value, nil
}

// 压栈
func (as *ArrayStack) Push(value interface{}) error {

	if as.IsFull() {
		fmt.Println("该栈已满")
		return errors.New("该栈已满")
	}
	as.top++
	as.stack[as.top] = value
	return nil
}

// 查看栈顶的值
func (as *ArrayStack) Peek() interface{} {
	return as.stack[as.top]
}

// 打印栈
func (as *ArrayStack) PrintList() error {

	if as.IsEmpty() {
		fmt.Println("该栈为空，未找到任何数据")
		return errors.New("该栈为空，未找到任何数据")
	}

	for i := as.top; i >= 0; i-- {
		fmt.Printf("stack[%d]: %v\n", i, as.stack[i])
	}
	return nil
}

func main() {

	///**
	// 实例化
	stack1 := NewStack(8)

	// 压栈操作
	stack1.Push(1)
	stack1.Push(2)
	stack1.Push(3)
	stack1.Push(4)
	stack1.Push(5)
	stack1.Push("a")
	stack1.Push("b")
	stack1.Push("c")
	stack1.Push("d")
	stack1.Push("e")
	// 打印栈数据
	stack1.PrintList()
	fmt.Println("==============================")
	// 弹栈
	val, _ := stack1.Pop()
	fmt.Printf("栈弹出的值为：%v\n", val)
	fmt.Println("==============================")
	stack1.PrintList()
}

// 是否为操作符
func IsOperator(op string) bool {
	switch op {
	case "+", "-", "*", "/", "(", ")":
		return true
	default:
		return false
	}
}

// 优先级
func Priority(op string) int {
	switch op {
	case "*", "/":
		return 2
	case "+", "-":
		return 1
	default:
		return 0
	}
}

// 计算
func Compute(op string, num1, num2 int) int {
	switch op {
	case "*":
		return num1 * num2
	case "/":
		return num1 / num2
	case "+":
		return num1 + num2
	case "-":
		return num1 - num2
	default:
		return 0
	}
}

// 字符串类型转整数类型
func string_to_int(str string) int {
	num, err := strconv.Atoi(str)

	if err != nil {
		fmt.Println("转换失败")
	}
	return num
}

/*
中缀表达式转化为后缀表达式
1. 遍历中缀表达式字符串
	1.1 如果遇到操作数就存入后缀表达式变量中
	1.2 如果遇到操作符('*','+','-','/','(')，新建一个栈来存储操作符:
		1.2.1 如果是'('，压入栈中
		1.2.2 如果是')', 则将栈中的操作符存入后缀表达式变量中，直到在栈中读取到'('
		1.2.3 如果不是'(', ')'， 比较该操作符与栈顶的操作符的优先级
			1.2.3.1 如果该操作符的优先级比栈顶操作符的优先级高，则入栈
			1.2.3.2 反之，将栈顶的操作符取出(pop())放入后缀表达式变量中，重复1.2.3步操作，直到将其压入栈中
2. 遍历完中缀表达式后，读取栈中数据，如栈中还有操作符，将其依次pop()取出存入后缀表达式变量中
*/

// 生成后缀表达式
func GenerateSuffixexpression(exp string) (suffixExpression string, err error) {
	// 实例化一个栈来暂存操作符
	stack := NewStack(len(exp))
	for _, e := range exp { // 1步骤
		char := string(e)

		if IsOperator(char) {
			if char == "(" { // 1.2.1
				stack.Push(char)
			} else if char == ")" { // 1.2.2
				for {
					if stack.IsEmpty() {
						err = errors.New("表达式错误，请检查！")
						return
					}
					if stack.Peek().(string) == "(" {
						stack.Pop()
						break
					}
					tmp, _ := stack.Pop()
					suffixExpression += tmp.(string)
				}
			} else { // 1.2.3
				for {
					if stack.IsEmpty() {
						break
					}
					tmp := stack.Peek().(string)
					if Priority(char) > Priority(tmp) { // 1.2.3.1
						break
					}
					suffixExpression += tmp
					stack.Pop()
				}
				stack.Push(char)
			}
		} else { // 1.1
			suffixExpression += char
		}
	}

	// 遍历完中缀表达式后，查看栈中是否还有数据，如有，则取出追加到后缀表达式变量中
	for { //2
		if stack.IsEmpty() {
			break
		}
		tmp, _ := stack.Pop()
		suffixExpression += tmp.(string)
	}
	fmt.Println("中缀表达式：", exp)
	fmt.Println("后缀表达式：", suffixExpression)
	return
}

// 计算后序表达式
func Calculate(exp string) {
	stack := NewStack(len(exp))

	for _, e := range exp {
		char := string(e)

		// 如果是运算符
		if IsOperator(char) {
			if stack.IsEmpty() {
				break
			}
			num2, _ := stack.Pop()
			num1, _ := stack.Pop()
			x1 := string_to_int(num1.(string))
			x2 := string_to_int(num2.(string))
			rs := fmt.Sprintf("%d", Compute(char, x1, x2))

			stack.Push(rs)

			fmt.Printf("Caclulate() %d %s %d = %s\n", x1, char, x2, rs)

		} else { // 如果是数字
			stack.Push(char)
			fmt.Println("Caclulate() char:", char)
		}
	}

	if !stack.IsEmpty() {
		res, err := stack.Pop()
		if err != nil {
			fmt.Println("Pop()异常")
			return
		}
		fmt.Println("表达式运算结果为：", res)
	}

}

func main() {
	/*使用栈实现计算字符串表达式*/
	res, err := GenerateSuffixexpression("5*(3*4+(3+2))+(5+3)/2")
	if err != nil {
		fmt.Println("异常")
	}
	fmt.Println("==============================")
	Calculate(res)

}