题解 | #表达式求值#

package main
import (
	"fmt"
	"strconv"
)
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
*/
func solve( s string ) int {
    str := s
	//中缀表达式转数组
	arr := change2Arr(str)
	//中缀表达式 =》逆波兰表达式
	polan := change2Polan(arr)
	//计算结果
	return computePolan(polan)
}

func change2Arr(s string) []string {
	arr := make([]string, 0)
	size := len(s)
	for i := 0; i < size; {
		//数字
		if s[i] >= '0' && s[i] <= '9' {
			num := 0
			for ; i < size && s[i] >= '0' && s[i] <= '9'; i++ {
				num = num*10 + int(s[i]-'0')
			}
			str := strconv.Itoa(num)
			arr = append(arr, str)
		} else {
			//()加减乘除
			arr = append(arr, string(s[i]))
			i++
		}
	}
	return arr
}

func change2Polan(arr []string) []string {
	//存放运算符栈
	stack1 := make([]string, 0)
	//存放数字栈，这是最终的逆波兰表达式
	stack2 := make([]string, 0)
	for i := 0; i < len(arr); i++ {
		//遍历到（
		if arr[i] == "(" {
			stack1 = append(stack1, arr[i])
		} else if arr[i] == "+" || arr[i] == "-" || arr[i] == "*" || arr[i] == "/" {
			//遍历到运算符
			//当前运算符优先级不大于stack1的栈顶运算符
			for len(stack1) != 0 && stack1[len(stack1)-1] != "(" && !comparePriovity(arr[i], stack1[len(stack1)-1]) {
				stack2 = append(stack2, stack1[len(stack1)-1])
				stack1 = stack1[:len(stack1)-1]
			}
			//运算符入栈
			stack1 = append(stack1, arr[i])
		} else if arr[i] == ")" {
			//遍历到)
			for len(stack1) != 0 && stack1[len(stack1)-1] != "(" {
				stack2 = append(stack2, stack1[len(stack1)-1])
				stack1 = stack1[:len(stack1)-1]
			}
			//剔除(
			stack1 = stack1[:len(stack1)-1]
		} else {
			//遍历到数字
			stack2 = append(stack2, arr[i])
		}
	}
	//将剩余的符号取出来
	for len(stack1) != 0 {
		stack2 = append(stack2, stack1[len(stack1)-1])
		stack1 = stack1[:len(stack1)-1]
	}
	return stack2
}

func comparePriovity(sign1, sign2 string) bool {
	if (sign1 == "+" || sign1 == "-") && (sign2 == "+" || sign2 == "-") ||
		(sign1 == "*" || sign1 == "/") && (sign2 == "*" || sign2 == "/") {
		return false
	}
	if (sign1 == "+" || sign1 == "-") && (sign2 == "*" || sign2 == "/") {
		return false
	}
	if (sign1 == "*" || sign1 == "/") && (sign2 == "+" || sign2 == "-") {
		return true
	}
	return false
}

func computePolan(polan []string) int {
	stack := make([]int, 0)
	for i := 0; i < len(polan); i++ {
		//运算符
		if polan[i] == "+" || polan[i] == "-" || polan[i] == "*" || polan[i] == "/" {
			num1 := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			num2 := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res := compute(num2, num1, polan[i])
			stack = append(stack, res)
		} else {
			//数字
			num, _ := strconv.Atoi(polan[i])
			stack = append(stack, num)
		}
	}
	return stack[0]
}

func compute(num1, num2 int, sign string) int {
	switch sign {
	case "+":
		return num1 + num2
	case "-":
		return num1 - num2
	case "*":
		return num1 * num2
	case "/":
		return num1 / num2
	default:
		return 0
	}
}

/*
*
输入：
"(2*(3-4))*5"

返回值：
-10

输入：
"3+2*3*4-1"

返回值：
26
*/
func main1() {
	//s := "(20*(3-4))*5" // -100
	//s := "2+(3-4)*5" // -3
	s := "3+2*3*4-1" // 26
	fmt.Println(solve(s))
}