中缀表达式转后缀表达式以及后缀表达式合法性验证

最近由于一项需求，需要用户自己来组合表达式，然后做运算，对于计算机处理数学计算，一般是先将中缀表达式，也就是我们平常见到的数学表达式转化为后缀表达式，

如 (2+3)*6 转换成 2 3 + 6 *，

后缀表达式中，是不含有括号的，计算机在运算的时候，从左向右读取，若遇到运算符，则取运算符左边的两个操作数来计算，并将计算结果作为下一次计算的一个操作数。

下面分享一个用JAVA实现的中缀转后缀并实现后缀表达式合法性的验证

 

 

 

 /**
	 * 中缀表达式转后缀表达式
	 * 
	 * @param formula
	 *            中缀表达式
	 * @return 后缀表达式
	 */
	public static String midToBehind(String formula) {
		String S = ""; // 后缀
		StringTokenizer st1 = new StringTokenizer(formula);
		String[] Operators = new String[st1.countTokens()];

		int Top = -1;
		while (st1.hasMoreTokens()) {
			String C = st1.nextToken();
			;
			switch (C.charAt(0)) {
			case ' ':
				break;
			case '+': // 操作符
			case '>':
			case '<':
			case '-':
				while (Top >= 0) // 栈不为空时
				{
					String c = Operators[Top--]; // pop Operator
					if (c.equals("(")) {
						Operators[++Top] = c; // push Operator
						break;
					} else {
						S = S + c;
					}
				}
				Operators[++Top] = C; // push Operator
				S += " ";
				break;
			case '*': // 操作符
			case '/':
				while (Top >= 0) // 栈不为空时
				{
					String c = Operators[Top--]; // pop Operator
					if (c.equals("(")) {
						Operators[++Top] = c; // push Operator
						break;
					} else {
						if (c.equals("+") || c.equals("-")) {
							Operators[++Top] = c; // push Operator
							break;
						} else {
							S = S + c;
						}
					}
				}
				Operators[++Top] = C; // push Operator
				S += " ";
				break;
			case '(': // 操作符
				Operators[++Top] = C;
				S += " ";
				break;
			case ')': // 操作符
				while (Top >= 0) // 栈不为空时
				{
					String c = Operators[Top--]; // pop Operator
					if (c.equals("(")) {
						break;
					} else {
						S = S + c;
					}
				}
				S += " ";
				break;
			default: // 操作数
				S = S + C + " ";
				break;
			}
		}
		while (Top >= 0) {
			S = S + Operators[Top--]; // pop Operator
		}

		System.out.println(S); // 后缀

		return S;
	}

	/**
	 * 检查后缀表达式是否正确
	 * 
	 * @param lpszParse
	 *            后缀表达式
	 * @return true 合法 false 不合法
	 */
	public static boolean checkBehind(String lpszParse) {

		int Otp = -1;
		boolean returnFlag = true;
		if (lpszParse != null) {
			// 后缀表达式不含有括号
			if (lpszParse.contains("(") || lpszParse.contains(")")) {
				return false;
			}

			// 分割表达式
			StringTokenizer st1 = new StringTokenizer(lpszParse);
			String[] Operands = new String[st1.countTokens()];
			while (st1.hasMoreTokens()) {
				String s = st1.nextToken();
				switch (s.charAt(0)) {
				case ' ':

				case '+':
				case '-':
				case '*':
				case '/':
				case '>':
				case '<':
					// 如果为运算符，刚将操作数出栈，如果小于两个操作数，则不正确
					if (Otp < 1) {
						returnFlag = false;
					} else {

						// 若存在两个操作数，则将两个操作数出栈
						String o1 = Operands[Otp--];
						String o2 = Operands[Otp--];

						// 将运算结果做为一个操作数，入栈，供下一次运算
						Operands[++Otp] = o1 + "&" + o2;
					}
					break;
				default:

					// 若为操作数，则入栈
					Operands[++Otp] = s;
				}

				// 如果存在不合法，跳出循环
				if (!returnFlag) {
					break;
				}
			}
			// 运算完成，栈内应该只剩最后一次运算的结果
			if (--Otp >= 0) {
				returnFlag = false;
			}
		}

		// 检测结果近回
		return returnFlag;
	}