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

ExpresstionConvert.java

package com.weirhp.interview;

import java.util.ArrayDeque;

/**
 * 将后缀表达式转为中缀表达式，满足：
 * 
 * <pre>
 * example 1:'56 34 213.7 + * 678 -'
 * 56 * (34 + 213.7) - 678
 * example 2:'1 56 35 + 16 9 - / +'
 * 1 + (56 + 35) / (16 - 9)
 * 
 * <pre>
 * @author weirhp@gmail.com
 * 2012-5-17
 * 
 */
public class ExpresstionConvert {
	private ArrayDeque<Expresstion> expStack = null;
	private String suffixExp = null;

	public ExpresstionConvert(String suffixExp) {
		this.suffixExp = suffixExp;
		expStack = new ArrayDeque<Expresstion>();
	}

	public String covertToMiddleExp() {
		String[] items = suffixExp.split(" ");
		for (int i = 0; i < items.length; i++) {
			if (isEmpty(items[i]))
				continue;
			if (isOperationChar(items[i])) {
				Expresstion secondExp = expStack.poll();
				Expresstion firstExp = expStack.poll();
				Expresstion resultExp = countExp(firstExp, secondExp, items[i]);
				expStack.push(resultExp);
			} else {
				expStack.push(new Expresstion(items[i], null));
			}
		}
		return expStack.pop().value;
	}

	private Expresstion countExp(Expresstion firstExp, Expresstion secondExp,
			String operation) {
		StringBuilder resultValue = new StringBuilder();
		if (isEmpty(firstExp.operation)
				|| expGt(firstExp.operation, operation)) {
			resultValue.append(firstExp.value);
		} else {
			resultValue.append("(").append(firstExp.value).append(")");
		}
		resultValue.append(" ");
		resultValue.append(operation);
		resultValue.append(" ");
		if (isEmpty(secondExp.operation)
				|| expGt(secondExp.operation, operation)) {
			resultValue.append(secondExp.value);
		} else {
			resultValue.append("(").append(secondExp.value).append(")");
		}
		return new Expresstion(resultValue.toString(), operation);
	}

	private boolean expGt(String expOp, String operation) {
		if (inArr(expOp, "+", "-") && inArr(operation, "*", "/")) {
			return false;
		} else if (inArr(expOp, "*") && inArr(operation, "/")) {
			return false;
		}
		return true;
	}


	public boolean inArr(String str, String... strArr) {
		if (str == null)
			return false;
		for (int i = 0; i < strArr.length; i++) {
			if (str.equals(strArr[i])) {
				return true;
			}
		}
		return false;
	}

	public boolean isOperationChar(String cha) {
		String[] operations = { "+", "-", "*", "/" };
		for (int i = 0; i < operations.length; i++) {
			if (operations[i].equals(cha))
				return true;
		}
		return false;
	}

	public boolean isEmpty(String str) {
		return str == null || str.isEmpty();
	}

	static class Expresstion {
		public Expresstion(String value, String operation) {
			this.value = value;
			this.operation = operation;
		}

		public String operation = null;
		public String value = null;
	}

	public static void main(String[] args) {
		System.out.println("56 34 213.7 + * 678 -:\n"
				+ new ExpresstionConvert("56 34 213.7 + * 678 -")
						.covertToMiddleExp());
		System.out.println("1 56 35 + 16 9 - / +:\n"
				+ new ExpresstionConvert("1 56 35 + 16 9 - / +")
						.covertToMiddleExp());
	}

}