粗浅看 逆波兰式算法
来源：程序员人生 发布时间：2016-07-20 08:49:51 阅读次数：3493次
简介
逆波兰表达式是1种10分有用的表达式，它将复杂表达式转换为可以依托简单的操作得到计算结果的表达式。它的优势在于只用两种简单操作，入栈和出栈就能够弄定任何普通表达式的运算。
实现逆波兰式的算法，难度其实不大，但为何要将看似简单的中序表达式转换为复杂的逆波兰式？缘由就在于这个简单是相对人类的思惟结构来讲的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。由于计算机普遍采取的内存结构是栈式结构，它履行先进后出的顺序。
在程序设计中，可能碰到需要对字符串数学表达式求值的问题，经常使用的方法是解析表达式，生成2叉树，然落后行计算。编译器就是使用这类方法来解析程序中的表达式的。这类方法实现起来有点难度，需要斟酌运算符的优先级，括号的配对，堆栈的使用等等。我们正常情况下看到的数学表达式如果用2叉树遍历的话，恰好是中序遍历，故叫做中序表达式。除此以外，还有前序表达式，后序表达式。如：a+b+c(中序)，++abc(前序)，ab+c+(后序)，如果表达式含有×，／，（）等就更复杂了。
后缀表达式也称逆波兰表达式 因其使表达式求值变得轻松，所以被普遍使用。
优先级
优先级分为栈内优先级isp(In stack priority)和栈外优先级icp(In coming priority)。除括号之外，其他运算符进栈后优先级都升1，这样可以体现在中缀表达式中相同优先级的操作符自左向右计算的要求，让位于栈顶的操作符先退栈并输出。各运算符及符号优先级：
逆波兰式
逆波兰式（Reverse Polish Notation, RPN）同样成为后缀表达式，更加广为人知1些，和前缀表达式恰好相反，是将操作符号放置于操作数以后，比如2 + 3 * (5 - 1)用逆波兰式来表示则是：2 3 5 1 - * +。
逆波兰式的计算也是从左往右顺次读取，当读到操作符时，将之前的两个操作数做计算，然后替换这两个操作数和操作符，接着读取，重复此步骤。对这个表达式，读到5 1 -，得到4，然后读取乘号，取出前面的3和上1步的计算结果4，并计算，到12，接着读取加号+，计算2 12 +得到14，计算结束。
上面这个步骤可以很容易的用栈来实现：
从左往右顺次读取表达式，如果是数字则将该数字压栈，如果是符号，则将之前的两个数字出栈，做计算后，将计算结果压栈，直到表达式读取结束。栈中剩下的1个数就是计算结果。
逆波兰式看起来像波兰式反过来，比如5 + 1的波兰式是+ 5 1，逆波兰式为5 1 +或1 5 +。也很明显，逆波兰式其实不是简单的将波兰式反过来，由于，减法和除法中减数和被减数、除数与被除数是不能交换的，即- 10 5和- 5 10就完全不1样。
Demo
基于JAVA语言
public class InversePoland {
// 9+(3⑴)*3+10/2 = 20
//private static String[] ss = new String[]{"9","+","(","3","-","1",")","*","3","+","10","/","2"};
//24+3⑻*(6⑶)*2+10⑶
private static String[] ss = new String[]{"24","+","3","-","8","*","(","6","-","3",")","*","2","+","10","-","3"};
private static Stack<String> stack = new Stack<String>();
//判断是不是为数字
private boolean isNum(String s) {
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")")) {
return false;
}
return true;
}
//获得符号优先级
private int getPriority(String s) {
if (s.equals("+") || s.equals("-")) {
return 1;
} else if (s.equals("*") || s.equals("/")) {
return 2;
}
return ⑴;
}
//输出字符串
private void print(String s) {
System.out.print(s + " ");
}
//符号操作
private void symbolOperation(String s) {
if (stack.size() == 0 || s.equals("(")) { //栈为空，直接进栈
stack.push(s);
} else if (s.equals(")")) { //当前字符为“）”,则将栈中（以上的全部出栈输出
while (stack.size() > 0) {
String pop_s = stack.pop();
if(pop_s.equals("(")) {
break;
} else {
print(pop_s);
}
}
} else {
int pri_s = getPriority(s);
while (stack.size() > 0 ) {
String top_s = stack.lastElement();
if (top_s.equals("(")) {
stack.push(s);
return;
} else {
int top_pri = getPriority(top_s);
if (pri_s <= top_pri) {
String pop_s = stack.pop();
print(pop_s);
} else {
break;
}
}
}
stack.push(s);
}
}
public void test() {
for (String s : ss) {
if (isNum(s)) {
print(s);
} else {
symbolOperation(s);
}
}
while (stack.size() > 0) {
String pop_s = stack.pop();
print(pop_s);
}
}
}
输出结果
24 3 + 86 3 - * 2 * - 10 + 3 –
业务思想
关于逆波兰式的学习，是对堆和栈的深入理解，对学习数据结构和算法是必要的。
感受1下逆波兰式的思考方式，你收获甚多！
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
