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