将标准表达式（中缀表达式）转换成后缀表达式_中缀表达式转后缀表达式

什么是后缀表达式

后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
例如：
这里我给出一个中缀表达式：a+bc-(d+e)
第一步：按照运算符的优先级对所有的运算单位加括号：式子变成了：((a+(bc))-(d+e))
第二步：转换前缀与后缀表达式
前缀：把运算符号移动到对应的括号前面
则变成了：-( +(a (bc)) +(de))
把括号去掉：-+abc+de 前缀式子出现
后缀：把运算符号移动到对应的括号后面
则变成了：((a(bc)* )+ (de)+ )-
把括号去掉：abc*+de+ - 后缀式子出现
发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。

将中缀表达式转换为后缀表达式

思路：
当读到操作数时，立即把它放到输出中。遇到操作符或左括号时不立即输出，先将其推入栈中。

进栈规则：

• 如果是操作符，那么从栈中弹出栈元素并写到输出中，直到发现优先级更低的元素或左括号为止。有一个例外：除非是在处理一个对应右括号时，否则我们绝不从栈中弹出左括号。
• 如果读到一个右括号，那么就将栈元素弹出，将弹出的符号写出直至遇到一个对应的左括号，但是这个左括号只被弹出并不输出。
• 最后，如果读到输入的末尾，我们将栈元素弹出并写到输出中，直到该栈变成空栈。

注：下面的代码对中缀表达式做了括号匹配检测（熟悉括号匹配原理的可以忽略）如何实现括号配对

2019/8/5 添加幂运算可快速求解高次幂（利用Java大整数类实现高次幂运算）例：2¹⁰⁰⁰ , 2 ^ 2 ^ 3 = 2⁸ = 256

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

import org.omg.CORBA.INITIALIZE;

public class 中缀到后缀的转换 {
	
	private static Vector<Character> leftVtor;//记录左括号
	private static Vector<Character> rightVtor;//记录右括号
	private static Vector<Character> charVtor;//记录操作符
	
	static {
		leftVtor = new Vector<>();
		leftVtor.add('(');
		leftVtor.add('[');
		leftVtor.add('{');
		
		rightVtor = new Vector<>();
		rightVtor.add(')');
		rightVtor.add(']');
		rightVtor.add('}');
		
		charVtor = new Vector<>();
		charVtor.add('+');
		charVtor.add('-');
		charVtor.add('*');
		charVtor.add('/');
		charVtor.add('^');
	}
	
	public static void main(String[] args) throws Exception {
		String s = "{1-[2*3+(4*5^2^ 2+6^2)]}/7";
		String ss = "-1+2*3+(4*5+6)*7";
		String sss = "-1^2+(2+-3)*-2^2";
		List<String> lst = infix2Postfix(sss);
		for (String i : lst) {
			System.out.print(i + " ");	
		}
	}
	/**
	 * 将中缀表达式转换为后缀表达式
	 * 
	 * 思路：
	 * 当读到操作数时，立即把它放到输出中。遇到操作符或左括号时不立即输出，先将其推入栈中。
	 * 进栈规则：
	 * 如果是操作符，那么从栈中弹出栈元素并写到输出中，直到发现优先级更低的元素或左括号为止。有一个例外：除非是在处理一个对应右括号时，否则我们绝不从栈中弹出左括号。
	 * 如果读到一个右括号，那么就将栈元素弹出，将弹出的符号写出直至遇到一个对应的左括号，但是这个左括号只被弹出并不输出。
	 * 最后，如果读到输入的末尾，我们将栈元素弹出并写到输出中，直到该栈变成空栈。
	 * 
	 * 时间复杂度：O(N)
	 * @param s 包含中缀表达式的字符串
	 * @return 经转换后的后缀表达式的顺序表
	 * @throws Exception
	 */
	public static List<String> infix2Postfix(String s) throws Exception {
		//将s中的操作数、操作符、括号分离出来，并检验表达式是否合法
		List<String> inPut = dissociator(s);
		
		//打印分离后中缀的表达式
		for (String i : inPut) {
			System.out.print(i + " ");				
		}
		System.out.println();
		
		//利用栈将中缀表达式转换成后缀表达式，stack用来存放操作符和括号
		Stack<Character> stack = new Stack<>();
		
		//记录转换后的后缀表达式
		List<String> outPut = new ArrayList<>();
		
		for (int i = 0; i < inPut.size(); i++) {
			//获取第一个字符
			String x = inPut.get(i);
			char c = x.charAt(x.length() - 1);
			
			//取幂运算符
			if(c == '^') {
				String str = inPut.get(i-1);
				while(c == '^' || Character.isDigit(c)) {
					str += x;
					i++;
					if(i < inPut.size()) {
						x = inPut.get(i);
						c = x.charAt(x.length() - 1);
					}else {
						break;
					}
				}
				outPut.set(outPut.size() - 1, 取幂运算.powOfpow(str).toString());
			}
			if(i < inPut.size()) {
				if(c >= '0' && c <= '9') {	
					//当遇到操作数时，将其添加到outPut中
					outPut.add(x);
				}else {
					/**
					 * 当遇到操作符或左括号时，将其压入栈中，并确保压入栈中操作符的优先级高于从栈顶到左括号或栈底的每个操作符（操作符优先级伪升序排列）。
					 * 除非正在处理右括号否则左括号不会从栈中弹出
					 */
					
					//如果栈空 或 栈顶元素是左括号 或 c是左括号 或 c的优先级大于栈顶元素，将c压入栈中。
					if(stack.isEmpty() || leftVtor.contains(stack.peek()) || leftVtor.contains(c) || priority(c) > priority(stack.peek())) {
						stack.add(c);					
					}else {
						
						/**
						 * 将优先级大于等于c的操作符从栈中弹出，并添加到outPut中。
						 * 当遇到栈空或左括号时停止，然后将c压进栈中或删除左括号。
						 */
						
						//若栈不为空并且栈顶元素不是左括号并且栈顶元素的优先级大于等于c，则将栈顶元素弹出，并添加到outPut中。
						//注：这里合并了c为右括号的情况，并规定括号的优先级小于操作符的优先级。
						while(!stack.isEmpty() && !leftVtor.contains(stack.peek()) && priority(stack.peek()) >= priority(c)) {
							outPut.add("" + stack.pop());
						}
						
						//如果c是右括号，则删除栈顶元素（此时栈顶元素为左括号）
						if(rightVtor.contains(c)) {
							stack.pop();
						}else {//将当前操作符压入栈中
							stack.add(c);
						}
					}
					
				}
			}
		}
		
		//读到输入末尾，将栈中的元素全部弹出并添加到outPut中。
		while(!stack.isEmpty()) {
			outPut.add("" + stack.pop());
		}
		
		return outPut;
	}
	
	/**
	 * 返回指定字符的优先级
	 * @param c 指定字符
	 * @return c的优先级
	 */
	public static int priority(char c) {
		//这里规定括号的优先级小于运算符的优先级，便于infix2Postfix中读到右括号时的弹栈操作。
		if(c == '{' || c == '}') return 1;
		if(c == '[' || c == ']') return 2;
		if(c == '(' || c == ')') return 3;
		
		if(c == '+' || c == '-') return 4;
		if(c == '*' || c == '/') return 5;
		return 0;
	}
	
	/**
	 * 将中缀表达式的操作数、操作符、括号分离出来，并顺序的保存到顺序表中。
	 * @param s 中缀表达式
	 * @return 经处理后记录后缀表达式的顺序表。
	 * @throws Exception 操作数与操作符之间不平衡。
	 */
	public static List<String> dissociator(String s) throws Exception {
		
		//这里检验中缀表达式中的括号是否合法
		if(!平衡符号.isValid(s)) {
			throw new Exception("括号未匹配");			
		}
		
		//保存后缀表达式的顺序表
		List<String> lst = new ArrayList<>();
		
		//记录操作数、操作符的个数
		int numCnt = 0, charCnt = 0;
		char c;
		int i = 0;
		//是否允许出现带有符号的操作数，初始化为true，当遇到操作数时变为false（意味着下一个元素必须为操作符），当遇到操作符是变为true（意味着下一个元素必须为操作数）。
		boolean f = true;
		while(i < s.length()) {
			c = s.charAt(i);
			String k = "";
			//带有符号的操作数（正、负）
			if(f && charVtor.contains(c)) { 
				k += c;
				do {
					i++;
					c = s.charAt(i);
				}while(i < s.length() && c == ' ');
			}
			
			//记录操作数
			while(i < s.length() && Character.isDigit(c)) {
				f = false;
				k += c;
				i++;
				if(i < s.length()) {
					c = s.charAt(i);					
				}else {
					break;
				}
			}
			
			//如果k不为空，则说明k可能为操作数
			if(!k.equals("")) {
				//检查k是否为合法操作数
				if(Character.isDigit(k.charAt(k.length()-1))) {
					lst.add(k);
					numCnt++;
				}else {
					throw new Exception("操作数不合法");
				}
			}
			
			if(i < s.length()) {
				//经过上面的while循环后, 此时的c一定不是数字。
				if(c != ' ') {
					lst.add("" + c);
					if(charVtor.contains(c)) {
						f = true;
						charCnt++;
					}
				}
				i++;
			}
		}
		
		if(numCnt == charCnt + 1) {
			return lst;
		}else {			
			throw new Exception("操作数与操作符数量不均衡");
		}
	}

}

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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233