百度百科
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
用途
逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+
优势
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
运算方法
1.创建两个栈，一个用来存放运算符stack1，一个用来存放最终结果stack2，遍历字符串；
a>如果是数字，直接压入stack2；
b>如果是是运算符且栈为空，直接压入stack1，如果栈不为空，当前运算符与栈顶运算符比较，如果优先级高于栈顶运算符直接压入，小于等于则，先把小于等于部分的运算符弹出到stack2中，再把扫描到的运算符压入到stack1中；
c>如果是'(',则无条件入栈，当遇到')'的时候，直接把括号内的部分弹出到stack2中，且括号不能入栈，输出的栈中是没有括号这个运算符的；
举例说明
a+bc +(d-e)f,运算符栈为s1,存放输出结果的栈为s2；
1.遇到数字a，直接入栈s2;此时s1：null ; s2:a
2.遇到+号且s1为空，直接入栈s1;此时：s1:+ ; s2:a
3.遇到数字b，直接入栈s2;此时：s1:+ ; s2:ab
4.遇到*号，优先级高于+号，直接入栈s1;此时：s1:+* ; s2:ab
5.遇到数字b，直接入栈s2;此时：s1:+* ; s2:abc
6.遇到+号,且运算符优先级低于s1栈顶符号，号弹出到s2;此时：s1:+ ; s2:abc;又等于此时s1的栈顶元素+号，继续弹出到s2;此时：s1:null ; s2:abc+;然后把+号直接压入s1;此时：s1:+ ; s2:abc*+
7.遇到（的时候，无条件压入s1;此时：s1:+( ; s2:abc*+
8.遇到d的时候，压入s2;此时：s1:+（ ; s2:abc*+d
9.遇到-号的时候，压入s1；此时：s1:+（- ; s2:abc*+
10.遇到e的时候，直接压入s2；此时：s1:+（- ; s2:abc*+e
11.遇到）的时候，把括号内部分还存在的运算符压入到 s2;此时：s1:+ ; s2:abc*+-
12.遇到号的时候，运算符优先级比s1栈顶元素+号高，直接压入s1;此时：s1:+ ; s2:abc*+-
13.遇到数字f直接压入s2;此时：s1:+ ; s2:abc+-f
14.此时把s1中的运算符号依次压入到s2;此时：s1:null ; s2:abc+-f+
此时，一个运算结束，其他表达式同样的操作进行即可；
代码实现
import java.util.Stack;
/**
* 逆波兰表达式
*/
public class ReversePolishNotation {
public static void main(String[] args) {
//测试用例
//String str = "1+2*3-4*5-6+7*8-9"; //123*+45*-6-78*+9-
String str = "a*(b-c*d)+e-f/g*(h+i*j-k)"; // abcd*-*e+fg/hij*+k-*-
//String str = "6*(5+(2+3)*8+3)"; //6523+8*+3+*
//String str = "a+b*c+(d*e+f)*g"; //abc*+de*f+g*f
Stack<Character> operators = new Stack<>(); //运算符
Stack output = new Stack(); //输出结果
rpn(operators, output, str);
System.out.println(output);
}
public static void rpn(Stack<Character> operators, Stack output, String str) {
char[] chars = str.toCharArray();
int pre = 0;
boolean digital; //是否为数字（只要不是运算符，都是数字），用于截取字符串
int len = chars.length;
int bracket = 0; // 左括号的数量
for (int i = 0; i < len; ) {
pre = i;
digital = Boolean.FALSE;
//截取数字
while (i < len && !Operator.isOperator(chars[i])) {
i++;
digital = Boolean.TRUE;
}
if (digital) {
output.push(str.substring(pre, i));
} else {
char o = chars[i++]; //运算符
if (o == '(') {
bracket++;
}
if (bracket > 0) {
if (o == ')') {
while (!operators.empty()) {
char top = operators.pop();
if (top == '(') {
break;
}
output.push(top);
}
bracket--;
} else {
//如果栈顶为 ( ，则直接添加，不顾其优先级
//如果之前有 ( ，但是 ( 不在栈顶，则需判断其优先级，如果优先级比栈顶的低，则依次出栈
while (!operators.empty() && operators.peek() != '(' && Operator.cmp(o, operators.peek()) <= 0) {
output.push(operators.pop());
}
operators.push(o);
}
} else {
while (!operators.empty() && Operator.cmp(o, operators.peek()) <= 0) {
output.push(operators.pop());
}
operators.push(o);
}
}
}
//遍历结束，将运算符栈全部压入output
while (!operators.empty()) {
output.push(operators.pop());
}
}
}
enum Operator {
ADD('+', 1), SUBTRACT('-', 1),
MULTIPLY('*', 2), DIVIDE('/', 2),
LEFT_BRACKET('(', 3), RIGHT_BRACKET(')', 3); //括号优先级最高
char value;
int priority;
Operator(char value, int priority) {
this.value = value;
this.priority = priority;
}
/**
* 比较两个符号的优先级
*
* @param c1
* @param c2
* @return c1的优先级是否比c2的高，高则返回正数，等于返回0，小于返回负数
*/
public static int cmp(char c1, char c2) {
int p1 = 0;
int p2 = 0;
for (Operator o : Operator.values()) {
if (o.value == c1) {
p1 = o.priority;
}
if (o.value == c2) {
p2 = o.priority;
}
}
return p1 - p2;
}
/**
* 枚举出来的才视为运算符，用于扩展
*
* @param c
* @return
*/
public static boolean isOperator(char c) {
for (Operator o : Operator.values()) {
if (o.value == c) {
return true;
}
}
return false;
}
}
