栈，是比较基础，应用比较广的一种数据结构，栈和队列都可以看成是比较特殊的一些链表，其最突出的特性就是先进后出。虾米阿尼是一个比较常见的中缀表达式求值的应用，当然中缀式到后缀式的转化也是可以实现的。

　　中缀式，这个我们不陌生平时大家写的式子就是中缀式的，比如2*（3-1）+（5+6）/9

　　后缀式，主要考虑的是操作符的位置，操作符在操作数之后的，比如上面的中缀式可以转化为这样的后缀式：2 3 1 - * 5 6 + 9 / +，转化的规则其实也很简单，opnd1 optr opnd2 ==>opnd1 opnd2 optr，大白话来说就是直接把操作符挪到两个操作数的后面，当然了，这里的opnd不单单就是一个数有时可能是中缀式中括号里面的一坨:-)。

　　表达式求值这一块的内容，本人参看的是以前读数据结构时的经典教材，严蔚敏老师的。

　　表达式求值的基本原理是一种常见的简明算法，“算符优先文法”，依稀记得这也是编译原理中曾经介绍过的，那么究竟什么是算符优先文法，通俗而言就是我们小学计算四则混合运算的规则：

1）先乘除，后加减

2）同级运算，从左到右依次计算

3）有括号的，先算括号里面的

　　具体到我们要说的，算符优先文法来看，考察一个式子，比如上面的2*（3-1）+（5+6）/9，这个式子中，我们规定“()”也是一种运算而且这种运算的优先级还比较的高。于是集合上面三条运算的规则，我们可以指定出来一个算符优先级表，计算机扫面表达式，通过查表，获得当前计算的动作。

首先我们先定义我们的运算符表 OP = {+-*/()#},并且我们结合上面的三条运算规则，定义出下面的运算符优先级表：

	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=	>
)	>	>	>	>		>
#	<	<	<	<	<		=

观察上面的表格，以第一行为例，当前计算机同时碰到了+和另外一种（也有可能是+）的运算，这是选择运算级别比较高的那种运算，上面  > 说明出在行位置的运算比列位置的运算的优先级高，反则反之，=表明二者的优先级一样，空格表示这两种运算之间没有可比性，说明输入的式子有文法错误。很明显我们要把上面的这个表存储到计算机中，以便计算机在计算的时候方便计算机来查阅，我们一般使用一个二维数组来存储。还有上面的 # 使我们加入的一种运算，我们规定这种运算的优先级最低。

　　下面就来简述一下，算法核心的流程。

需要两个栈，扫描中缀表达式时，用optr栈存储中缀式里面的运算符，用opnd栈存储中缀式中的运算数。optr栈顶的运算符对应着算符优先级表第一纵裂位置的运算符，每次从中缀式总扫描到的运算符，对应着优先级表第一横行位置的运算符。于是算法的基本思想如下：

（1）首先置操作数栈为空栈，然后置optr运算符栈的栈底为#运算。

（2）依次扫描表达式中的每一个字符ch，若是操作数则压入opnd栈中，若是运算符则和optr栈顶的运算符比较优先级后做相应的操作（若栈顶运算符优先级高则opnd连续弹出两个数完成相应运算再把记过压入opnd中，如果optr栈顶运算符优先级低，则把当前扫描到的运算符压入optr栈中），直至整个表达式扫描完毕，这是opnd中的数值就是运算结果。

具体的描述如下，

/*                                                                                           * 中缀表达式的 求值计算                                                                               */                                                                                         public void inffixCal()                                                                     {                                                                                               int index = 0;                                                                                                                                                                          while(inffixExp.charAt(index)!='#' || optr.peekFirst()!='#')                                {                                                                                               Character ch = inffixExp.charAt(index);                                                     if(!inOP(ch))                                                                               {
    // 一般数字                                                                                        opnd.push(Double.parseDouble(ch+""));    //于是准备取下一个字符了                                       index ++;                                                                               }                                                                                           else{
   // 运算符                                                                                     switch(Precede(optr.peekFirst(), ch))                                                       {                                                                                               case -1:    // < 栈顶 符号 的优先级 低 符号入栈                                                              optr.push(ch);                                                                              index ++;                                                                                   break;                                                                                                                                                                              case 1:        // > 即栈顶符号的优先级比较高                                                                   Character theta = optr.pop();                                                               Number b = (Double) opnd.pop();                                                             Number a = (Double) opnd.pop();                                                             Double c = operate(a, b, theta);                                                            opnd.push(c);        // 把计算的结果再次压站                                                           break;                                                                                                                                                                              case 0:    // 两种运算符的优先级相等 也就是 ()                                                                   optr.pop();    //脱括号之后 接着往后扫描                                                                  index ++;                                                                                   break;                                                                                  default:                                                                                        throw new RuntimeException(new Exception("您的文法有误，请检查"));                            }                                                                                       }                                                                                       }                                                                                           result = (Double)opnd.pop();                                                            }

算法的实现，定义了一个expressionEvaluate类，具体的实现详见下面的代码，展看查看详情

1 package test;  2   3 import java.util.LinkedList;  4 import java.util.Scanner;  5   6 import javax.naming.InitialContext;  7   8 /*  9  * 基于"算符优先"文法 的表达式求值， 其实这也是数据程序编译器设计中常用的一种方法 10  * 其实可以一次性 扫描中缀表达式的同时，利用算符文法来求出中缀表达式的值，由于中缀式和后缀式的相互转化使用的也是算法文法，这里就把问题分开两部分来做 11  * 提前说一下，个人总是感觉，算法设计类的问题总是比较适合面向过程来解决，这里硬是面向对象感觉有点伪面向对象的感觉 12  * ExpressionEvaluate    算法的主体驱动部分 13  */ 14  15 public class ExpressionEvaluate { 16      17     public static final String OP = "+-*/()#";    //求值系统的所有算附表 18     public static final int[][] opPreTable={    //算符优先级表 19         {1, 1, -1, -1, -1, 1, 1}, 20         {1, 1, -1, -1, -1, 1, 1}, 21         {1, 1, 1, 1, -1, 1, 1}, 22         {1, 1, 1, 1, -1, 1, 1}, 23         {-1, -1, -1, -1, -1, 0, Integer.MAX_VALUE}, 24         {1, 1, 1, 1, Integer.MAX_VALUE, 1, 1}, 25         {-1, -1, -1, -1, -1, -Integer.MAX_VALUE, 0} 26     }; 27      28     // 定义两个工作栈 29     private LinkedList
      
        optr;    // 存储操作符 30     private LinkedList
        opnd;    //存储数字 31     private StringBuffer inffixExp;        //    存储中缀表达式 32     private StringBuffer suffixExp;        //存储后缀表达式 33     private double result;                //表达式最终的结果 34      35     {
    // 构造代码块 优先于 构造函数的执行 36         init();    //初始化操作 37     } 38     public ExpressionEvaluate() { 39          40     } 41     public ExpressionEvaluate(String exp) 42     { 43         setInffixExp(exp); 44     } 45      46     public void setInffixExp (String exp) 47     { 48         inffixExp = new StringBuffer(exp); 49         if(inffixExp.charAt(inffixExp.length()-1)!='#') 50             inffixExp.append('#'); 51     } 52      53     private void init() 54     { 55         inffixExp = new StringBuffer(); 56         suffixExp = new StringBuffer(); 57         optr = new LinkedList
       
        (); 58         opnd = new LinkedList
        
         (); 59         optr.push('#'); 60         result = 0; 61     } 62      63     public String getInffix() 64     { 65         return new String(inffixExp.substring(0, inffixExp.length()-1)); 66     } 67     public String getSuffix() 68     { 69         return new String(suffixExp); 70     } 71     public Double getResult() 72     { 73         return result; 74     } 75      76     /* 77      * 中缀表达式的 求值计算 78      */ 79     public void inffixCal() 80     { 81         int index = 0; 82          83         while(inffixExp.charAt(index)!='#' || optr.peekFirst()!='#') 84         { 85             Character ch = inffixExp.charAt(index); 86             if(!inOP(ch)) 87             {
    // 一般数字 88                 opnd.push(Double.parseDouble(ch+""));    //于是准备取下一个字符了 89                 index ++; 90             } 91             else{
    // 运算符 92                 switch(Precede(optr.peekFirst(), ch)) 93                 { 94                     case -1:    // < 栈顶 符号 的优先级 低 符号入栈 95                         optr.push(ch); 96                         index ++; 97                         break; 98                          99                     case 1:        // > 即栈顶符号的优先级比较高100                         Character theta = optr.pop();101                         Number b = (Double) opnd.pop();102                         Number a = (Double) opnd.pop();103                         Double c = operate(a, b, theta);104                         opnd.push(c);        // 把计算的结果再次压站105                         break;106                         107                     case 0:    // 两种运算符的优先级相等 也就是 ()108                         optr.pop();    //脱括号之后 接着往后扫描109                         index ++;110                         break;111                     default:112                         throw new RuntimeException(new Exception("您的文法有误，请检查"));113                 }114             }115         }116         result = (Double)opnd.pop();117     }118     119     public double operate(Number a, Number b, Character theta) {120         double c = 0;121         switch(theta)122         {123             case '+':124                 c = (Double)a + (Double)b;125                 break;126             case '-':127                 c = (Double)a - (Double)b;128                 break;129             case '*':130                 c = (Double)a * (Double)b;131                 break;132             case '/':133                 if((Double)b == 0)134                     throw new RuntimeException(new Exception("除数不能为0"));135                 c = (Double)a / (Double)b;136                 break;137             default:138                 throw new RuntimeException(new Exception("尚不支持这种运算"));139         }140         return c;141     }142     /*143      * 比较栈optr栈顶符号 和 当前符号之间的优先级144      */145     public int Precede(Character peekFirst, Character ch) {146         return opPreTable[OP.indexOf(peekFirst)][OP.indexOf(ch)];147     }148     // 判断某个字符是不是在 运算符表中149     public boolean inOP(Character ch)150     {151         return OP.contains(new String (ch+""));152     }153     154     /*155      * 中缀表达式到后缀表达式156      * 和 中缀式 求值 非常相似157      */158     public void inffix2suffix()159     {160         suffixExp.setLength(0);161         optr.clear();162         opnd.clear();163         int index = 0;164         165     }166     167     public static void main(String[] args) {168 /*        String exp;169         Scanner scanner = new Scanner(System.in);    // 2*(5-1)/2+3-1170         171         System.out.println("输入一个以#结尾的表达式");172         exp = scanner.next();*/173         174         ExpressionEvaluate ee = new ExpressionEvaluate();175         ee.setInffixExp("2*3*4-1#");176         177         System.out.println(ee.getInffix());178         179         ee.inffixCal();180         181         System.out.println(ee.getResult());182         183         184     }185     186 }
        
       
      

上面就只实现了中缀表达式的求值，可以进一步完善，inffix2suffix中缀式到后缀式的转化，这里没有实现了，如果实现之后，具体的表达式的计算可以先把中缀式转化为后缀式，计算结果时简单的扫描后缀式就可以计算了，因为后缀式是一种无需担心运算符优先级的算式表达形式。

下面是inffix---》suffix转化的算法描述

(1)标识符号#压入optr栈中，开始扫描终追表达式

(2)当ch!='#'时

　　if ch>=0 && ch <=9 opnd.push(ch)

　　if ch is a operator 

　　　　if ch > optr.top()　　optr.push(ch)

　　　　if ch < optr.top()　　opnd连续出两个操作数，并和当前的栈顶运算符附加到suffix中

　　　　if ch==optr.top()　　查看上面的运算符优先级表可以知道，(==)这时候直接把optr的(弹出即可，然后接着向后扫描表达式