题解 | #表达式求值#

• 将()里的式子看成一个sub-equation，进行递归
• 若遇到 + -，push
• 若遇到 * /，栈的top与新数字计算并放回栈的top

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	inputReader := bufio.NewReader(os.Stdin)
	for {
		input, err := inputReader.ReadString('\n')
		if err != nil {
			break
		}
		input = strings.Trim(input, "\r\n")
		input = trimSpace(input)
		res := calc(input)
		fmt.Println(res)
	}
}

func calc(s string) int {
	nums := make([]int, 0)

	// 在第一个数字或者(之前加正号
	if isDigit(s[0]) || s[0] == '(' {
		s = "+" + s
	}
	// 将第一个符号给sign，sign可为+，可为-
	sign := s[0]
	num := 0
	i := 1
	for i < len(s) {
		// 遇到右括号则)直接忽略
		if s[i] == ')' {
			i++
			continue
		}

		// 若是数字，则获取到整个数字，做运算
		if isDigit(s[i]) {
			count := 0
			num, count = getNum(s[i:])
			if count == 0 {
				break
			}
			nums = baseCalc(nums, num, sign)

			i += count
		} else { // 若是符号，(左括号则进入递归，)则忽略，
			if s[i] == '(' {
				subStr, count := getSubEqt(s[i+1:]) // 跳过'('
				num = calc(subStr)
				nums = baseCalc(nums, num, sign)
				i += count
			}
			// )不可以赋值给sign，sign只能是+,-,*,/
			if s[i] != ')' {
				sign = s[i]
			}
			i++

		}
	}
	sum := 0
	for _, v := range nums {
		sum += v
	}
	return sum
}

func baseCalc(nums []int, num int, sign byte) []int {
	if len(nums) == 0 {
		if sign == '+' {
			nums = append(nums, num)
		} else if sign == '-' {
			nums = append(nums, -num)
		}
	} else if sign == '+' {
		nums = append(nums, num)
	} else if sign == '-' {
		nums = append(nums, -num)
	} else if sign == '*' {
		nums[len(nums)-1] = nums[len(nums)-1] * num
	} else if sign == '/' {
		nums[len(nums)-1] /= num
	}
	return nums
}

func isDigit(v byte) bool {
	if v >= '0' && v <= '9' {
		return true
	}
	return false
}

func getNum(s string) (int, int) {
	numStr := ""
	i := 0
	for _, v := range s {
		if isDigit(byte(v)) {
			numStr += string(v)
			i++
		} else {
			break
		}
	}
	num, _ := strconv.Atoi(numStr)
	return num, i
}

func getSubEqt(s string) (string, int) {
	paraCount := 0
	subStr := ""
	for i, v := range s {
		if v == ')' && paraCount == 0 {
			return subStr, i
		}
		if v == '(' {
			paraCount++
		}
		if v == ')' {
			paraCount--
		}
		subStr += string(v)
	}
	return "", 0
}

func trimSpace(s string) string {
	res := ""
	for _, v := range s {
		if v != ' ' {
			res += string(v)
		}
	}
	return res
}