题解 | #表达式求值#

package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */

// 定义操作符与运算函数的映射
var operatorFuncMap = map[string]func(a, b int) int{
	"+": func(a, b int) int { return a + b },
	"-": func(a, b int) int { return a - b },
	"*": func(a, b int) int { return a * b },
}

// 实现计算器逻辑
func solve(expr string) int {
	// 用栈存储数字
	nums := []int{}
	// 用栈存储运算符
	ops := []string{}

	// 辅助索引和临时结果
	index, result := 0, 0

	// 遍历表达式字符
	for ; index < len(expr); index++ {
		// 如果是数字,则解析整数并存入nums栈
		if expr[index] >= '0' && expr[index] <= '9' {
			num := 0
			for ; index < len(expr) && expr[index] >= '0' && expr[index] <= '9'; index++ {
				num = num*10 + int(expr[index]-'0')
			}
			nums = append(nums, num)
			index--
			// 如果是左括号,则直接存入ops栈
		} else if expr[index] == '(' {
			ops = append(ops, string(expr[index]))
			// 如果是右括号,则连续从nums和ops栈弹出数据进行运算,直到遇到左括号为止
		} else if expr[index] == ')' {
			for ops[len(ops)-1] != "(" {
				result = operatorFuncMap[ops[len(ops)-1]](nums[len(nums)-2], nums[len(nums)-1])
				nums = nums[:len(nums)-2]
				nums = append(nums, result)
				ops = ops[:len(ops)-1]
			}
			ops = ops[:len(ops)-1]
			// 如果是运算符,则从ops栈弹出运算符,进行运算,并将结果和新运算符 push 入栈
		} else {
			for len(ops) > 0 && precedence(ops[len(ops)-1]) >= precedence(string(expr[index])) {
				result = operatorFuncMap[ops[len(ops)-1]](nums[len(nums)-2], nums[len(nums)-1])
				nums = nums[:len(nums)-2]
				nums = append(nums, result)
				ops = ops[:len(ops)-1]
			}
			ops = append(ops, string(expr[index]))
		}
	}

	// 将栈中剩余元素弹出计算,得到最终结果
	for len(ops) > 0 {
		result = operatorFuncMap[ops[len(ops)-1]](nums[len(nums)-2], nums[len(nums)-1])
		nums = nums[:len(nums)-2]
		nums = append(nums, result)
		ops = ops[:len(ops)-1]
	}

	return nums[0]
}

// 定义运算符的优先级
func precedence(op string) int {
	if op == "+" || op == "-" {
		return 1
	} else if op == "*" {
		return 2
	} else {
		return 0
	}
}