例如:3+2*6-2
先定义两个栈,一个为数值栈,一个为运算符栈;
stack.go
package stack
import (
"errors"
"fmt"
)
type Stack struct {
MaxTop int //栈最大可以存放的数量
Top int //栈顶
Arr [20]int //模拟栈
}
func (s *Stack) Push(val int) (err error) {
//先判断栈是否满了
if s.Top == s.MaxTop-1 {
fmt.Println("栈满了")
return errors.New("栈满了")
}
s.Top++
s.Arr[s.Top] = val
return
}
func (s *Stack) Pop() (val int, err error) {
if s.Top == -1 {
fmt.Println("栈已空")
return -1, errors.New("栈已空")
}
val = s.Arr[s.Top]
s.Arr[s.Top] = 0
s.Top--
return val, nil
}
func (s *Stack) Show() {
if s.Top == -1 {
fmt.Println("栈为空")
return
}
tmp := s
for i := tmp.Top; i >= 0; i-- {
fmt.Printf("Arr[%d]=%v\n", i, tmp.Arr[i])
}
return
}
//判断一个字符是数字还是加减乘除
func (s *Stack) IsOper(val int) bool {
if val == 42 || val == 43 || val == 45 || val == 47 {
return true
} else {
return false
}
}
//运算的方法
func (s *Stack) Cal(num1 int, num2 int, 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 *Stack) Priority(oper int) int {
res := 0
if oper == 42 || oper == 47 {
res = 1
} else if oper == 43 || oper == 45 {
res = 0
}
return res
}
main.go
package main
import (
"fmt"
"go_code/data_structure/stack"
"strconv"
)
func main() {
str := "30+2*6-600/2"
n := len(str)
numStack := &stack.Stack{
MaxTop: n,
Top: -1,
}
operStack := &stack.Stack{
MaxTop: n,
Top: -1,
}
index := 0
num1 := 0
num2 := 0
oper := 0
result := 0
keepNum := ""
for {
ch := str[index : index+1]
//字符对应的ASCII码值
tmp := int([]byte(ch)[0])
if operStack.IsOper(tmp) {
if operStack.Top == -1 {
operStack.Push(tmp)
} else {
//判断栈顶的优先级
if operStack.Priority(operStack.Arr[operStack.Top]) >=
operStack.Priority(tmp) {
num1, _ = numStack.Pop()
num2, _ = numStack.Pop()
oper, _ = operStack.Pop()
result = operStack.Cal(num1, num2, oper)
//将计算的结果重新入栈
numStack.Push(result)
//当前符号重新入栈
operStack.Push(tmp)
} else {
operStack.Push(tmp)
}
}
} else {
//判断型如30等数字
keepNum += ch
if index == n-1 {
val, _ := strconv.ParseInt(keepNum, 10, 64)
numStack.Push(int(val))
} else {
//向index后面探以位
if operStack.IsOper(int([]byte(str[index+1 : index+2])[0])) {
val, _ := strconv.ParseInt(keepNum, 10, 64)
numStack.Push(int(val))
keepNum = ""
}
}
//入栈的数要是int型
// val, _ := strconv.ParseInt(ch, 10, 64)
// numStack.Push(int(val))
}
if index == n-1 {
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)
}
res, _ := numStack.Pop()
fmt.Printf("计算表达式 %v 的值是:%v\n", str, res)
}
运行结果: