一、预处理
给定任意四则运算的字符串表达式（中缀表达式），preDeal预先转化为对应的字符串数组，其目的在于将操作数和运算符分离。
例如给定四则运算内的中缀表达式：
String infix = "100+8*5-(10/2)*5+10.5";
字符串数组化后得：
{"100","+","8","*","5","-","(","10","/","2",")","+","10.5"}
二、中缀表达式转后缀表达式
规则：
遍历中缀表达式，
A、如果遇到操作数直接输出
B、如果遇到运算符，分情况：
B1：如果是*、/或者(这三个运算符，直接压栈
B2：如果是)，则出栈直到遇到(位置。（左括号和有括号并不参与拼接后缀表达式）。
B3：如果是+或者-，先弹栈直到栈空，再讲当前的+或者-压栈。
其中情况B可以总结：
遇到右括号出栈直到匹配左括号，遇到操作符，如果其优先级高于栈顶元素，则继续压栈，否则出栈。
三、计算后缀表达式
规则：
遍历后缀表达式：
A、遇到操作数压栈
B、遇到运算符则将栈顶和次栈顶两个元素取出参与对应的运算，再将运算结结果压栈。
四、Java算法实现
package agstring;
import java.util.*; public class RPN {
public static String[] preDeal(String infix){
infix = infix.trim();
int length = infix.length();
ArrayList<String> infixOfArrayList = new ArrayList<String>();
char currChar;
int index = 0;
final String regex = "\\+|-|\\*|\\/|\\(|\\)";
for (int i = 0; i < length; i++) {
currChar = infix.charAt(i);
if(String.valueOf(currChar).matches(regex)){//运算符
if (index < i) {
infixOfArrayList.add(infix.substring(index,i));//add数字
}
infixOfArrayList.add(String.valueOf(currChar));
index = i+1;
}
}
infixOfArrayList.add(infix.substring(index,length));
return infixOfArrayList.toArray(new String[infixOfArrayList.size()]);
}
public static String[] getPostfix(String infix) {
String[] infixOfAry = preDeal(infix);
int length = infixOfAry.length;
ArrayDeque<String> stack = new ArrayDeque<String>();
String currString = "";
final String regex = "\\+|-|\\*|\\/|\\(|\\)";
ArrayList<String> postfixOfArrayList = new ArrayList<String>();
for (int i = 0; i < length; i++) {
currString = infixOfAry[i];
if (currString.matches(regex)) {//symbol
if (currString.matches("\\*|\\/|\\(")) {
stack.offerFirst(currString);
}else {//),+,-
String top = "";
if(currString.equals(")")){
while(!stack.isEmpty()){
top = stack.removeFirst();
if (top.equals("(")) {
break;
}
postfixOfArrayList.add(top);
}
}else {//+ ,-
if (!stack.isEmpty()) {
top = stack.peekFirst();
if (top.equals("*") || top.equals("/")) {
while(!stack.isEmpty()){
postfixOfArrayList.add(stack.removeFirst());
}
}
}
stack.offerFirst(currString);
}
}
}else {//number
postfixOfArrayList.add(currString);
}
}
while(!stack.isEmpty()){
postfixOfArrayList.add(stack.removeFirst());
}
return postfixOfArrayList.toArray(new String[postfixOfArrayList.size()]);
}
public static double computePostfix(String infix){
String[] postfixAry = getPostfix(infix);
ArrayDeque<Double> stack = new ArrayDeque<Double>();
int length = postfixAry.length;
String currString = "";
final String regex = "\\+|-|\\*|\\/|\\(|\\)";
double operandOne,operandTwo;
for (int i = 0; i < length; i++) {
currString = postfixAry[i];
if (currString.matches(regex)) {
operandOne = stack.removeFirst();
operandTwo = stack.removeFirst();
switch (currString.charAt(0)) {
case '+':
stack.addFirst(operandTwo + operandOne);
break;
case '-':
stack.addFirst(operandTwo - operandOne);
break;
case '*':
stack.addFirst(operandTwo * operandOne);
break;
case '/':
stack.addFirst(operandTwo / operandOne);
break;
} }else {
stack.addFirst(Double.parseDouble(currString));
}
}
return stack.removeFirst();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
String infix = "100+8*5-(10/2)*5+10.5";
double result = computePostfix(infix);
System.out.println(result);
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
} }
（完）