2014
01.06

逆波兰表达式将操作符置于操作数的后面。比如,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, /, *]

 


Hit Counter by http://yizhantech.com/