码农的博客

逆波兰表达式将操作符置于操作数的后面。比如，3+4用逆波兰表示法则是 “3 4 +”。 更复杂的，7+8*2 则是 “7 8 2 * +”。

将算术表达式转换成逆波兰表达式的算法如下：

1. 分配2个栈，栈s1用于临时存储运算符（含一个结束符号）；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为’#’；

2. 从算术表达式的左端开始逐个读取字符x，逐序进行如下步骤：

（1）若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；

（2）若x是运算符，则分情况讨论：

若x是'(‘，则直接压入栈s1；

若x是’)’，则将距离栈s1栈顶的最近的'(‘之间的运算符，逐个出栈，依次压入栈s2，此时抛弃'(‘；

若x是除'(‘和’)’外的运算符，则再分如下情况讨论：

若当前栈s1的栈顶元素为'(‘，则将x直接压入栈s1；

若当前栈s1的栈顶元素不为'(‘，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s1的栈顶运算符为'(‘或”#”。最后再则将x压入栈s1;

3. 在进行完2后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括’#’）；

4. 完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底。

下面是java实现。

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

public class ReversePolishNotation {
	private final static String PLUS = "+";

	private final static String MINUS = "-";

	private final static String MULTIPLY = "*";

	private final static String DIVIDE = "/";

	private final static String POINT = ".";

	private final static String OPSTART = "(";

	private final static String OPEND = ")";

	private final static String NUMBER_SIGN = "#";

	private String exp;

	private List<String> expList = new ArrayList<String>();

	private List<String> rpnList = new ArrayList<String>();

	public ReversePolishNotation(String exp) {
		this.exp = exp;
	}

	private boolean isDigit(String str) {
		return str.equals("0") || str.equals("1") || str.equals("2")
				|| str.equals("3") || str.equals("4") || str.equals("5")
				|| str.equals("6") || str.equals("7") || str.equals("8")
				|| str.equals("9");
	}

	/**
	 * 是否是负号
	 * 
	 * @param exp
	 * @param ch
	 * @param index
	 * @return
	 */
	private boolean isNegativeSign(String exp, String ch, int index) {
		if (ch.equals("-")) {
			if (index == 0) {
				return true;
			} else {
				String previous = exp.substring(index - 1, index);
				if ((!isDigit(previous)) && (!(previous.equals(OPEND)))) {
					return true;
				} else {
					return false;
				}
			}
		}
		return false;
	}

	private void parse() {
		int length = exp.length();

		String tempStr = "";
		for (int i = 0; i < length; i++) {
			String tempChar = exp.substring(i, i + 1);
			if (isDigit(tempChar) || tempChar.equals(POINT)
					|| isNegativeSign(exp, tempChar, i)) {
				tempStr += tempChar;
			} else {
				if (!tempStr.equals("")) {
					expList.add(tempStr);
				}
				expList.add(tempChar);
				tempStr = "";
			}
		}
		if (!tempStr.equals("")) {
			expList.add(tempStr);
		}

	}

	private boolean isNumber(String str) {
		try {
			Double.parseDouble(str);
			return true;
		} catch (NumberFormatException e) {
			return false;
		}
	}

	/**
	 * 运算符str1 是否比str2优先级高
	 * 
	 * @param str1
	 * @param str2
	 * @return
	 */
	private boolean prior(String str1, String str2) {
		if ((str1.equals(MULTIPLY) || str1.equals(DIVIDE))
				&& (str2.equals(PLUS) || str2.equals(MINUS))) {
			return true;
		} else if ((str1.equals(PLUS) || str1.equals(MINUS)
				|| str1.equals(MULTIPLY) || str1.equals(DIVIDE))
				&& str2.equals(NUMBER_SIGN)) {
			return true;
		}
		return false;
	}

	/**
	 * 运算符str1 是否比str2优先级低
	 * 
	 * @param str1
	 * @param str2
	 * @return
	 */
	private boolean posterior(String str1, String str2) {
		if ((str1.equals(PLUS) || str1.equals(MINUS))
				&& (str2.equals(MULTIPLY) || str2.equals(DIVIDE))) {
			return true;
		} else if (str1.equals(NUMBER_SIGN)
				&& (str2.equals(PLUS) || str2.equals(MINUS)
						|| str2.equals(MULTIPLY) || str2.equals(DIVIDE))) {
			return true;
		}
		return false;
	}

	private void generateRPN() {
		Stack<String> s1 = new Stack<String>();
		s1.push(NUMBER_SIGN);
		Stack<String> s2 = new Stack<String>();
		for (int i = 0; i < expList.size(); i++) {
			String item = expList.get(i);
			if (isNumber(item)) {
				s2.push(item);
			} else if (item.equals(OPSTART)) {
				s1.push(item);
			} else if (item.equals(OPEND)) {
				String c;
				do {
					c = s1.pop();
					if (!c.equals(OPSTART)) {
						s2.push(c);
					}
				} while (!c.equals(OPSTART));
			} else {
				String top = s1.peek();
				if (top.equals("(")) {
					s1.push(item);
				} else {
					if (prior(item, top)) {
						s1.push(item);
					} else {
						String c;
						do {
							c = s1.pop();
							s2.push(c);
							if (posterior(s1.peek(), item)
									|| s1.peek().equals("(")
									|| s1.peek().equals(NUMBER_SIGN)) {
								break;
							}

						} while (true);
						s1.push(item);
					}
				}
			}
		}

		while (!s1.isEmpty()) {
			String c = s1.pop();
			if (!c.equals(NUMBER_SIGN)) {
				s2.push(c);
			}
		}
		rpnList = new ArrayList<String>();
		rpnList.addAll(s2);

	}

	public List<String> getRPN() {
		parse();
		generateRPN();
		return rpnList;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String exp = "7+8*2";
		ReversePolishNotation rpn = new ReversePolishNotation(exp);
		List<String> rpnExp = rpn.getRPN();
		System.out.println("算术表达式：" + exp);
		System.out.println("逆波兰表达式：" + rpnExp);

		exp = "(30-4*5)*(3+5)-5";
		rpn = new ReversePolishNotation(exp);
		rpnExp = rpn.getRPN();
		System.out.println("算术表达式：" + exp);
		System.out.println("逆波兰表达式：" + rpnExp);

		exp = "(8-4)*(88/2/11)";
		rpn = new ReversePolishNotation(exp);
		rpnExp = rpn.getRPN();
		System.out.println("算术表达式：" + exp);
		System.out.println("逆波兰表达式：" + rpnExp);
	}

}

控制台输出如下：

算术表达式：7+8*2
逆波兰表达式：[7, 8, 2, *, +]
算术表达式：(30-4*5)*(3+5)-5
逆波兰表达式：[30, 4, 5, *, -, 3, 5, +, *, 5, -]
算术表达式：(8-4)*(88/2/11)
逆波兰表达式：[8, 4, -, 88, 2, /, 11, /, *]