这应该是属于数据结构入门的部分，我大一的时候就应该写过，现在重新看数据结构，我决定在实现一遍
（这里 讨论的表达式只包含加减乘除 小括号）
简单来讲计算表达式的值可以通过计算表达式的后缀表达式的值来计算（注：我们通常讲的表达式都是中序表达式）
举例说明： A+B-C*D 这是我们要计算的表达式，我们知道*比+/-的优先级高，但是计算机并不能智能的识别并处理，所以我们需要告诉计算机这样的规则
其中一种做法就是将中序表达式转化成后序表达式 之前式子的后序表达式为 AB+CD*-，对于计算机来说他读到符号只需要入栈，读到符号只需要出栈2个数值，根据符号计算然后入栈数值就行了。
接下来是分析如何从中序转化成后序表达式，
1我们观察单一优先级的运算符
A-B+C AB-C+
A*B/C AB*C/
我们可以得知如果存在同意优先级的运算符连续连接多个数我们需要在读到第二个运算符时把之前的运算符输出（这样是保证了式子的从左到右的计算顺序）
2我们观察混合运算符
A+B*C ABC*+
A/B-C AB/C-
我们可以知道高优先级运算符会抢先于低优先级的运算符的执行，所以当我们读到低优先级的选算符必须把高优先级的运算符全部输出，
其实换个说法更好理解，我们可以把混合运算符连接的式子 高优先级运算符连接的部分看成一个整体 比如 A+B*C -》 A+（B*C） 我们对于高优先级的式子先计算是为了得出低优先级运算符的一个操作元，最后把式子转化成一个低优先级的运算符
3小括号
直接把小括号里的式子当做一个新的式子处理，处理的结果当做一个操作元
根据之前的观察结果 我们可以知道这样的转化规则，我们在处理中序表达式的时候，如果读到一个数，我们就直接输出，如果我们读到一个运算符，我们需要cache下来，并且把优先级不低于他的运算符全部输出，遇到小括号的时候，我们读入左括号，把括号内的式子按照正常处理，在读入右括号的时候 我们需要左括号内cache的符号依次输出，比如（A-B*C）
接下来放我写的demo，最近感冒 脑子有点不清楚，程序的冗余比较多，也可能存在一部分bug，不过我测试的几个案例都过了，如果程序有错请联系我。
程序是直接得到式子的结果，如果需要得到后序表达式 照着我上面说的思路改一改就可以了
import java.util.ArrayList;
//把只包含加减乘除和小括号以及操作元是正数的正确算数表达式以后缀表达式为中介计算求值
public class MidtoPost {
public static void main(String[] args) throws Exception {
System.out.println(MidtoPost.GetResult("20+"));
}
public MidtoPost() {
}
// 用一个栈结构存储中介值，也用一个栈存储算数符号
// 遇到一个数值先压栈，遇到一个算数符号，我把所有的优先级不低于于他的算数符号出栈，同时出栈2个数值，将计算结果出栈。
private static int pointer;// 只想当前正在处理的字符的位置
private static ArrayList<Double> NumStack = new ArrayList<Double>();
private static ArrayList<Character> MarkStack=new ArrayList<Character>();
private static char[] polo;
private static int size;
public static Double GetResult(String poloy){
polo = poloy.toCharArray();
size = poloy.length();
NumStack.clear();
MarkStack.clear();
double result = 0;
double cache2 = 0;
double cache1 = 0;
boolean condition = false;
try {
while (pointer < size) {
switch (polo[pointer]) {
// 遇到 +/- 将 乘除号弹出
case '+':
case '-':
condition = true;
while (condition && MarkStack.size() > 0) {
char tempMark = MarkStack.remove(MarkStack.size() - 1);
switch (tempMark) {
case '+':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 + cache2);
break;
case '-':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 - cache2);
break;
case '*':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 * cache2);
break;
case '/':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 / cache2);
break;
default:
MarkStack.add(tempMark);
condition = false;
break;
}
}
MarkStack.add(polo[pointer]);
pointer++;
break;
case '*':
case '/':
condition = true;
while (condition && MarkStack.size() > 0) {
char tempMark = MarkStack.remove(MarkStack.size() - 1);
switch (tempMark) {
case '*':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 * cache2);
break;
case '/':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 / cache2);
break;
default:
MarkStack.add(tempMark);
condition = false;
break;
}
}
MarkStack.add(polo[pointer]);
pointer++;
break;
case '(':
MarkStack.add('(');
pointer++;
break;
case ')':
char tempchar = MarkStack.remove(MarkStack.size() - 1);
while (tempchar != '(') {
switch (tempchar) {
case '+':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 + cache2);
break;
case '-':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 - cache2);
break;
case '*':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 * cache2);
break;
case '/':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 / cache2);
break;
default:
break;
}
tempchar = MarkStack.remove(MarkStack.size() - 1);
}
pointer++;
break;
default:
NumStack.add(GetNextNum());
break;
}
}
ClearMark();
return NumStack.get(0);
} catch (Exception e) {
System.err.println("表达式错误");
}
return Double.MAX_VALUE;
}
// 用来式子结束之后对符号栈进行清空操作
private static void ClearMark() throws Exception {
double cache1 = 0;
double cache2 = 0;
while (MarkStack.size() > 0) {
char tempchar = MarkStack.remove(MarkStack.size() - 1);
switch (tempchar) {
case '+':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 + cache2);
break;
case '-':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 - cache2);
break;
case '*':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 * cache2);
break;
case '/':
cache2 = NumStack.remove(NumStack.size() - 1);
cache1 = NumStack.remove(NumStack.size() - 1);
NumStack.add(cache1 / cache2);
break;
default:
throw new Exception("illegal mark");
}
}
}
// 获取下一个数值
private static Double GetNextNum() throws Exception {
if (pointer >= size) {
throw new Exception("out of border");
}
StringBuffer sb = new StringBuffer();
boolean condition = true;
while (condition) {
sb.append(polo[pointer]);
pointer++;
if (pointer >= size) {
return Double.parseDouble(sb.toString());
}
switch (polo[pointer]) {
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
condition = false;
break;
default:
break;
}
}
return Double.parseDouble(sb.toString());
}
}