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)) }