Ming
0%

计算表达式

Posted on Edited on In

一类经典的题目是，给定一个表达式，表达式根据操作符的种类数，是否考虑小数，形态各异，有针对于某一种形态的解法，也有很通用的办法：

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package main

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

// 优先级
var priority = make(map[rune]int)

// 数字栈
var nums []int

// 操作符栈（包含括号）
var ops []rune

// 暂时存储读到的数字
var numBuf bytes.Buffer

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for scanner.Scan() {
		exp := scanner.Text()
		val := calculate(exp)
		fmt.Println(val)
	}
}

func calculate(expression string) int {
	// 预处理
	expression = preprocess(expression)

	for i, ch := range expression {
		switch {
		case ch == '(':
			ops = append(ops, ch)
		case ch == ')': // 先算括号里面的
			numBufFlush()

			for {
				if ops[len(ops)-1] != '(' {
					cal()
				} else {
					ops = ops[:len(ops)-1]
					break
				}
			}
		case unicode.IsNumber(ch):
			numBuf.WriteRune(ch)
			if i == len(expression)-1 {
				numBufFlush()
			}
		case isOperator(ch):
			numBufFlush()

			for len(ops) != 0 && ops[len(ops)-1] != '(' {
				// 遇到操作符，计算栈内所有可计算的表达式（优先级大于等于当前操作符的）
				if priority[ops[len(ops)-1]] >= priority[ch] {
					cal()
				} else {
					break
				}
			}
			ops = append(ops, ch)
		}
	}

	// 残留
	for len(ops) != 0 {
		cal()
	}
	return nums[len(nums)-1]
}

func isOperator(ch rune) bool {
	if ch == '+' || ch == '-' || ch == '*' || ch == '/' {
		return true
	}
	return false
}

func numBufFlush() {
	num, err := strconv.Atoi(numBuf.String())
	// 空的numBuf
	if err != nil {
		return
	}
	nums = append(nums, num)
	numBuf.Reset()
}

// 用栈顶的数字和运算符计算一次
func cal() {
	if len(nums) <= 1 || len(ops) == 0 {
		return
	}

	a, b := nums[len(nums)-2], nums[len(nums)-1]
	nums = nums[:len(nums)-2]
	op := ops[len(ops)-1]
	ops = ops[:len(ops)-1]

	switch op {
	case '+':
		nums = append(nums, a+b)
	case '-':
		nums = append(nums, a-b)
	case '*':
		nums = append(nums, a*b)
	case '/':
		nums = append(nums, a/b)
	}
}

// 初始的替换
func preprocess(exp string) string {
	exp = strings.ReplaceAll(exp, "{", "(")
	exp = strings.ReplaceAll(exp, "[", "(")
	exp = strings.ReplaceAll(exp, "}", ")")
	exp = strings.ReplaceAll(exp, "]", ")")
	exp = strings.ReplaceAll(exp, " ", "")
	exp = strings.ReplaceAll(exp, "(-", "(0-")
	exp = strings.ReplaceAll(exp, "(+", "(0+")
	return exp
}

func init() {
	// 优先级定义
	priority['+'] = 0
	priority['-'] = 0
	priority['*'] = 1
	priority['/'] = 1

	// 表达式的第一个字符可能为正负号
	nums = append(nums, 0)
}

思路

使用两个栈：存放数字的栈 和 存放操作符的栈

  • 遇到数字：把整个数字入栈
  • 遇到操作符：比较栈顶操作符和当前操作符的优先级，如果栈顶操作符的优先级不低于当前操作符，就取栈顶的元素和操作符进行计算，将计算后的结果入栈。
  • 遇到括号：遇到左括号直接入栈，遇到右括号就不听的取栈顶元素和操作符计算，直到遇到左括号

最终栈顶的元素即为所求。

实际中还有很多特殊情况要考虑，比如表达式以正负号开头，含有空白字符等。