0%

栈的应用之中缀表达式和后缀表达式

发表于 更新于 分类于

中缀表达式： 是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法，但是不易被计算机所解析。

后缀表达式：是一个通用的算术或逻辑公式表示方法， 操作符是后缀形式处于操作数的后面（例：3 4 +），后缀表达式虽然不是人们所习惯的运算表示方法，但是易被计算机解析。

例如：对于中缀表达式 9+(3-1)*2+10/2 , 其后缀表达式是 9 3 1 - 3 * + 10 2 / + , 那么为了方便计算机解析计算，我们需要将中缀表达式转换成后缀表达式，然后再对后缀表达式进行解析。

1. 中缀表达式转后缀表达式：

  1. 当读到一个操作数时，立即将它放到输出中。读到的是操作符则需要接着判断是否该入栈。读到的是左圆括号则入栈。
  2. 在读到操作符时，如果栈为空或者栈顶操作符为（，则入栈。如果栈顶操作符不为（，且此操作符优先级小于或等于此时栈顶操作符，则将栈中元素弹出直至 ①遇到左括号 或者 ②栈顶元素为更低优先级 或者 ③栈为空为止，并将当前操作符入栈；否则当前操作符继续入栈。操作符中，+-优先级低，*/优先级高。
  3. 如果遇到一个右括号，那么就将栈中元素弹出并输出直至遇到左括号为止。但是这个左括号只被弹出，并不输出。
  4. 如果读到输入的末尾，若栈不为空则将栈元素弹出直到该栈变成空栈，并将弹出的符号写到输出中。

“9+(3-1)*2+10/2” 转换过程：

操作过程 栈中元素 输出
读入 9，输出 9
读入 +，栈为空，规则2，入栈 + 9
读入 ( ，左括号，规则1，入栈 + ( 9
读入 3，输出 + ( 9 3
读入 -，栈顶为（，规则2，入栈 + ( - 9 3
读入 1，输出 + ( - 9 3 1
读入 ) ，右括号，规则3，出栈并输出 + 9 3 1 -
读入 *，*优先级高于栈顶+，规则,2，入栈 + * 9 3 1 -
读入 3，输出 + * 9 3 1 - 3
读入 +，+优先级低于栈顶*，规则2，栈中元素出栈，当前操作符入栈 + 9 3 1 - 3 * +
读入 10， 输出 + 9 3 1 - 3 * + 10
读入 / ， /优先级高于+，入栈 + / 9 3 1 - 3 * + 10
读入 2， 输出 + / 9 3 1 - 3 * + 10
读至末尾，规则4，栈不为空，栈中元素出栈并输出 9 3 1 - 3 * + 10 / +

2. 后缀表达式计算最终结果：

  1. 从左到右遍历表达式的每个数字和符号,遇到是数字则进栈,遇到是运算符则将栈顶两个元素出栈,进行运算并将运算结果进栈；
  2. 遍历完后缀表达式,此时栈中剩余的数字就是运算结果。

“9 3 1 - 3 * + 10 2 / +” 计算过程：

操作过程 栈中元素
读入 9，入栈 9
读入 3，入栈 9 3
读入 1，入栈 9 3 1
读入 -，运算并将结果入栈 9 2
读入 3，入栈 9 2 3
读入 *，运算并将结果入栈 9 6
读入 +，运算并将结果入栈 15
读入 10，入栈 15 10
读入 2，入栈 15 10 2
读入 /，运算并将结果入栈 15 5
读入 +，运算并将结果入栈 20
读入完毕，栈中元素即为结果 20

简单中缀表达式计算的java实现：

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
public class SimpleCalcutor {

	private class Item {

		private String value;
		private Integer number;

		public Item(String value) {
			this.value = value;
			try {
				number = Integer.parseInt(value);
			} catch (Exception ignore) {
			}
		}

		public boolean isNumber() {
			return number != null;
		}

		public int getNumber() {
			if (isNumber())
				return number;
			throw new NumberFormatException();
		}

		public boolean isAdd() {
			return "+".equals(value);
		}

		public boolean isSub() {
			return "-".equals(value);
		}

		public boolean isMul() {
			return "*".equals(value);
		}

		public boolean isDiv() {
			return "/".equals(value);
		}

		public boolean isLeftBracket() {
			return "(".equals(value);
		}

		public boolean isRightBracket() {
			return ")".equals(value);
		}

		public int getPriority() {
			if (isAdd() || isSub())
				return 0;
			if (isMul() || isDiv())
				return 1;
			throw new RuntimeException("This is not +, -, *, /");
		}

		@Override
		public String toString() {
			return value != null ? value.toString() : null;
		}
	}

	/**
	 * 计算结果
	 * 
	 * @param calStr
	 * @return
	 */
	public int calculate(String calStr) {
		List<Item> infixes = parse(calStr);
		List<Item> postfixes = infix2postfix(infixes);
		return calculateByPostfix(postfixes);
	}

	/**
	 * 利用正则表达式将待计算的字符串转化为List<Item>形式 ,如 10/2 -> [10, /, 2]
	 * 
	 * @param calStr
	 * @return
	 */
	private List<Item> parse(String calStr) {
		Pattern pattern = Pattern.compile("\\D|\\d+");
		Matcher m = pattern.matcher(calStr);
		List<Item> items = new ArrayList<Item>();
		while (m.find()) {
			items.add(new Item(m.group(0)));
		}
		return items;
	}

	/**
	 * 中缀表达式转换为后缀表达式
	 * <p>
	 * 1.当读到一个操作数时，立即将它放到输出中。读到的是操作符则需要接着判断是否该入栈。读到的是左圆括号则入栈。<br>
	 * 2.如果遇到一个右括号，那么就将栈中元素弹出并输出直至遇到左括号为止。但是这个左括号只被弹出，并不输出。<br>
	 * 3.在读到操作符时，如果此操作符优先级小于或等于此时栈顶操作符，则将栈中元素弹出直至(1)遇到左括号或者(2)栈顶元素为更低优先级或者(3)
	 * 栈为空为止。操作符中，'+''-'优先级最低，'('')'优先级最高。 <br>
	 * 4.如果读到输入的末尾，将栈元素弹出直到该栈变成空栈，将符号写到输出中。
	 * 
	 * @return
	 */
	private List<Item> infix2postfix(List<Item> infixes) {
		List<Item> postfixes = new ArrayList<Item>();
		Stack<Item> stack = new Stack<Item>();
		for (Item item : infixes) {
			if (item.isNumber()) {
				postfixes.add(item);
			} else if (item.isRightBracket()) {
				// ) 右括号,将栈中元素弹出直至左括号,且左括号和右括号不加入到后缀表达式中
				while (true) {
					Item tmp = stack.pop();
					if (tmp.isLeftBracket())
						break;
					postfixes.add(tmp);
				}
			} else if (item.isLeftBracket()) {
				// ( 左括号,将左括号入栈
				stack.push(item);
			} else {
				// 当前操作符为 +, -, *, /,
				if (stack.isEmpty()) {
					// 操作符栈为空,则将当前操作符压入栈
					stack.push(item);
					continue;
				}
				Item top = stack.peek();
				if (top.isLeftBracket()) {
					// 操作符栈顶为左括号(,则将当前操作符压入栈
					stack.push(item);
					continue;
				}
				if (item.getPriority() <= top.getPriority()) {
					// 如果此操作符(+,-,*,/)优先级小于或等于此时栈顶操作符
					// 则将栈中元素弹出直至(1)遇到左括号或者(2)栈顶元素为更低优先级或者(3)栈为空为止
					// 并将弹出的元素加入后缀表达式中,将当前操作符压入栈中
					while (true) {
						Item tmp = stack.peek();
						if (tmp.isLeftBracket() || tmp.getPriority() < item.getPriority()) {
							break;
						}
						postfixes.add(tmp);
						stack.pop();
						if (stack.isEmpty())
							break;
					}
					stack.push(item);
				} else {
					// 如果当前操作符(+,-,*,/)优先级大于此时栈顶操作符,则将当前操作符压入栈
					stack.push(item);
				}
			}
		}
		// 如果栈中元素不为空,则将栈中元素全部弹出,加入后缀表达式中
		while (!stack.isEmpty()) {
			postfixes.add(stack.pop());
		}
		return postfixes;
	}

	/**
	 * 通过后缀表达式计算数值
	 * <p>
	 * 1. 从左到右遍历表达式的每个数字和符号,遇到是数字则进栈,遇到是运算符则将栈顶两个元素出栈,进行运算并将运算结果进栈<br>
	 * 2. 遍历完后缀表达式,此时栈中剩余的数字就是运算结果
	 * 
	 * @param postfixes
	 * @return
	 */
	private int calculateByPostfix(List<Item> postfixes) {
		Stack<Integer> stack = new Stack<Integer>();
		for (Item item : postfixes) {
			if (item.isNumber()) {
				stack.push(item.getNumber());
			} else {
				// 运算符
				int num1 = stack.pop();
				int num2 = stack.pop();
				int result;
				if (item.isAdd()) {
					result = num2 + num1;
				} else if (item.isSub()) {
					result = num2 - num1;
				} else if (item.isMul()) {
					result = num2 * num1;
				} else if (item.isDiv()) {
					result = num2 / num1;
				} else {
					throw new IllegalArgumentException("Operator invalid : " + item.value);
				}
				stack.push(result);
			}
		}
		return stack.pop();
	}

	public static void main(String[] args) {
		SimpleCalcutor calcutor = new SimpleCalcutor();
		String calStr = "9+(3-1)*3+10/2";
		int result = calcutor.calculate(calStr);
		System.out.println(result);
	}

}

源码github地址：
SimpleCalculator

参考链接：
利用栈将中缀表达式转换成后缀表达式