逆波兰表达式(后缀表达式求值)
##1 描述
计算后缀表达式 [9,3,1,-,3,*,+,10,2,/,+ ]
现在我们已经将表达式专为后缀表达式了，马上需要对这个表达式进行求值。
计算规则：
从左到右遍历每个数字，以及符号。
1）如果为数字，则进栈
2）如果为符号，则栈顶的2个数字出栈并进行计算。然后将结果入栈
一直到获取到最终结果。
package main
import (
"fmt"
"strconv"
)
/*
* 定义节点
*/
type Node struct {
data string
next *Node
}
/*
* 定义栈
*/
type Stack struct {
top *Node
length int
}
func NewStack() *Stack {
return &Stack{top: nil, length: 0}
}
/*
* 压栈
*/
func (list *Stack) Push(data string) error {
node := &Node{data: data, next: list.top}
list.top = node
list.length++
return nil
}
/*
* 出栈
*/
func (list *Stack) Pop() (string, error) {
if list.length == 0 {
return "", fmt.Errorf("the list is empty")
}
node := list.top
list.top = node.next
list.length--
return node.data, nil
}
/**************************************************/
//栈外优先级icp(In coming priority)
func GetIcp(oper string) int {
switch oper {
case ")":
return 1
case "(":
return 8
case "+":
fallthrough
case "-":
return 2
case "*":
fallthrough
case "/":
fallthrough
case "%":
return 4
case "#":
return 0
}
return 0
}
//栈内优先级isp(In stack priority)
func GetIsp(oper string) int {
switch oper {
case ")":
return 8
case "(":
return 1
case "+":
fallthrough
case "-":
return 3
case "*":
fallthrough
case "/":
fallthrough
case "%":
return 5
case "#":
return 0
}
return 0
}
func IsOperator(oper string) bool {
switch oper {
case "(":
fallthrough
case ")":
fallthrough
case "+":
fallthrough
case "-":
fallthrough
case "*":
fallthrough
case "/":
return true
default:
return false
}
return false
}
func DoOperator(oper string, number1 int, number2 int) int {
switch oper {
case "+":
return number1 + number2
case "-":
return number1 - number2
case "*":
return number1 * number2
case "/":
return number1 / number2
default:
return 0
}
return 0
}
func CenterToEnd(expr []string) []string {
stack := &Stack{top: &Node{data: "#", next: nil}, length: 0}
retexpr := make([]string, 0)
for _, v := range expr {
if !IsOperator(v) {
retexpr = append(retexpr, v)
} else {
if stack.length == 0 {
stack.Push(v)
} else {
//遇到")",则出栈并输出。直到"(","("出栈不输出。
if GetIcp(v) == 1 {
for GetIcp(stack.top.data) != 8 {
data, _ := stack.Pop()
retexpr = append(retexpr, data)
}
stack.Pop()
} else if GetIcp(v) >= GetIsp(stack.top.data) {
//比较运算符>的情况
stack.Push(v)
} else {
//比较运算符<=的情况
for GetIcp(v) < GetIsp(stack.top.data) {
data, _ := stack.Pop()
retexpr = append(retexpr, data)
}
stack.Push(v)
}
}
}
}
//输出栈中剩余计算符
for stack.length > 0 {
data, _ := stack.Pop()
retexpr = append(retexpr, data)
}
fmt.Println("后缀表达式:", retexpr)
return retexpr
}
func calculate(expr []string) string {
stack := &Stack{top: &Node{data: "#", next: nil}, length: 0}
//retexpr := make([]string, 0)
for _, v := range expr {
if !IsOperator(v) {
stack.Push(v)
} else {
str1, _ := stack.Pop()
str2, _ := stack.Pop()
number1, _ := strconv.ParseInt(str1, 10, 32)
number2, _ := strconv.ParseInt(str2, 10, 32)
number3 := DoOperator(v, int(number2), int(number1))
ret := strconv.FormatInt(int64(number3), 10)
stack.Push(ret)
}
}
result, _ := stack.Pop()
return result
}
func main() {
expr := []string{"9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"}
retexpr := CenterToEnd(expr)
fmt.Println("计算结果", calculate(retexpr))
}