表达式（四则运算）计算的算法

清疚 2022-08-18 14:25 155阅读 0赞

表达式（四则运算）计算的算法

# 戏剧前奏——基本知识点 #

通常我们所看到的算术表达式，运算符总是在两个操作数中间(除)，如(A+B)\*C，这样的表达式叫做**中缀表达式**。这种表达式不同的运算符优先级不同，而且通常含有括号，计算机很难理解这种表达式。在编译系统中，要把人易于理解的表达式翻译成能正确求值的机器指令。编译系统中对中缀形式的算术表达式的处理方式是: 先把中缀表达式转换成后缀表达式，再进行计算。

**后缀表达式**就是表达式中的运算符出现在操作数的后面，并且不含括号，如AB+C\*。后缀表达式的特点：

(1).后缀表达式让操作数和中缀表达式的操作数先后次序相同，只是运算符的先后次序改变；

(2).后缀表达式没有括号，运算次序就是其执行次序。

在计算机内部，任何一个表达式都是由操作数、运算符和分界符组成。操作数和运算符是表达式的主要部分，分界符(如用\#表示)标志了一个表达式的结束。我们把操作数、运算符和分界符称为表达式的**单词**。

一个中缀表达式的四则运算规则：

1.先乘除后加减

2.先括号内后括号外

3.同级别时先左后右

下面以A+(B-C/D)\*E为例对过程进行讲解。A+(B-C/D)\*E转换成后缀表达式后为

ABCD/-E\*+

其运算次序为：T1=CD/; T2=BT1-; T3=T2E\*; T4=AT3+。

基于后缀表达式的两个特点，计算过程如下：计算时只要从左到右依次扫描后缀表达式的各个**单词**，当读到的单词为运算符时，就对该运算他会前两个操作数进施以此运算所代表的操作，然后将结果T插入到后缀表达式中再重复上面的操作。

# 享受过程——实现步骤和方法 #

根据以上的讲解，可初步地列出实现的步骤如下：

1.把中缀表达式的字符中提取出一系列表达式单词；

2.把中缀表达式单词系列转换成后缀表达式单词系列；

3.对后缀表达式词系列依次进行计算。

下面依次对各个步骤进行讲解。

## 把中缀表达式的字符中提取出一系列表达式单词 ##

要提取表达式单词，首先要定义一个单词的类，判断该字符串是否是数字还是运算符

代码如下

/**
 	 * 判断当前字符或字符串是否是数字
 	 * 
 	 * @param str
 	 * @return
 	 */
 	public static boolean isNumber(String str) {
 		return str.startsWith("0") || str.startsWith("1")
 				|| str.startsWith("2") || str.startsWith("3")
 				|| str.startsWith("4") || str.startsWith("5")
 				|| str.startsWith("6") || str.startsWith("7")
 				|| str.startsWith("8") || str.startsWith("9")
 				|| str.startsWith(".");
 
 	}

将算式表达式转换成操作数和运算符，放入链表中

/**
 	 * 分析四则运算表达式，将数字与运算符进行分解
 	 */
 	public static List<String> parse(String exp) {
 		int length = exp.length();
 
 		// 四则运算解析
 		List<String> expList = new ArrayList<String>();
 
 		String tempStr = "";
 		for (int i = 0; i < length; i++) {
 			String tempChar = exp.substring(i, i + 1);
 			if (DataUtils.isNumber(tempChar)) {// 如果是数字的话
 				tempStr += tempChar;
 			} else {
 				if (!tempStr.equals("")) {// 遇到运算符，判断存储的数字字符串是否为空
 					expList.add(tempStr);
 				}
 				expList.add(tempChar);
 				tempStr = "";
 			}
 		}
 		if (!tempStr.equals("")) {// 保证最后一个非空的数字字符串添加到expList中
 			expList.add(tempStr);
 		}
 		return expList;
 	}

## 把中缀表达式单词系列转换成后缀表达式单词系列 ##

中缀表达式转换成后缀表达式的算法步骤：(1).设置一个堆栈S，初始时将栈顶元素设置为\#。(2).顺序读入中缀表达式，当读到的单词为操作数时将其加入到线性表L， 并接着读下一个单词。(3).令x1为当前栈顶运算符的变量，x2为当前扫描读到的运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2；然后比较x1与x2的优先级，若优先级x1>x2，将x1从S中出栈，并加入L中，接着比较新的栈顶运算符x1与x2的优先级；若优先级x1<x2，将x2入栈S，接着读下一个单词；若优先级x1=x2且x1为”(”而x2为”)”,将x1出栈，接着读下一个单词；若优先级x1=x2且x1为”\#”而x2为”\#”,算法结束。

**各运算符优先级关系表**

表中x1为\+或\-，x2为\*或/时，优先级x1<x2，满足中缀表达式规则1.先乘除后加减；x1为\+、\-、\*或/，x2为(或/时，优先级x1<x2，满足中缀表达式规则2.先括号内后括号外；当x1的运算符x2的运算符同级别时，优先级x1=x2，满足中缀表达式规则3.同级别时先左后右。出现表中的$表示中缀表达式语法出错。

**中缀表达式转换成后缀的过程**

<table style="color:rgb(85,85,85); font-size:15px; line-height:35px; font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"> 
 <tbody> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"> 步骤 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:solid solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-top-width:0.5pt; border-top-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 中序表达式 </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:solid solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-top-width:0.5pt; border-top-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 堆栈 </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:solid solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-top-width:0.5pt; border-top-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 输出 </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 1 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> A+(B-C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 2 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> +(B-C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> A </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 3 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> (B-C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+ </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> A </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 4 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> B-C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+( </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> A </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 5 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> -C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+( </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> AB </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 6 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> C/D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+(- </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> AB </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 7 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> /D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+(- </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABC </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 8 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> D)*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+(-/ </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABC </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 9 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> )*E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+(-/ </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 10 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> *E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+(- </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD/ </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 11 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> *E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+( </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD- </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 12 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> *E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+ </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD- </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 13 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> E# </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+* </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD- </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 14 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+* </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD-E </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 15 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> #+ </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD-E* </td> 
 </tr> 
 <tr> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> 16 </td> 
 <td style="width:106.5pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> # </td> 
 <td style="width:106.55pt; padding:0pt 5.4pt; border-style:none solid solid none; border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)"> ABCD-E*+ 
 <div> 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

/**
 	 * 将分解后的四则运算列表构建成逆波兰表达式列表
 	 */
 	public static List<String> createRPN(List<String> expList) {
 		Stack stack = new Stack();
 		// 存放逆波兰表达式
 		List<String> rpnList = new ArrayList<String>();
 
 		int length = expList.size();
 		for (int i = 0; i < length; i++) {
 			String c = expList.get(i);
 
 			// 如果是数字，直接放到逆波兰链表的最后
 			if (DataUtils.isNumber(c)) {
 				rpnList.add(c);
 			} else {
 				// 如果不是数字
 				// 如果是左括号，则直接将左括号压入栈
 				if (OperatorUtils.isParenthesesStart(c)) {
 					stack.push(c);
 				} else if (OperatorUtils.isParenthesesEnd(c)) {
 					// 如果是右括号
 
 					// 进行出栈操作，直到栈为空或者遇到第一个左括号
 					while (!stack.isEmpty()) {
 						// 将栈顶字符串做出栈操作
 						String tempC = stack.pop();
 						if (!tempC.equals(OperatorUtils.OPSTART)) {
 							// 如果不是左括号，则将字符串直接放到逆波兰链表的最后
 							rpnList.add(tempC);
 						} else {
 							// 如果是左括号，退出循环操作
 							break;
 						}
 					}
 				} else {
 					// 如果栈内为空
 					if (stack.isEmpty()) {
 						// 将当前字符串直接压栈
 						stack.push(c);
 					} else {
 						// 如果栈不为空
 
 						// 比较栈顶字符串与当前字符串的优先级
 						if (OperatorUtils.compare(stack.top(), c)) {
 							// 如果栈顶元素的优先级大于当前字符串,则进行出栈操作
 							// 将栈顶元素直接放到逆波兰链表的最后
 							// 直到栈内为空，或者当前元素的优先级不小于栈顶元素优先级
 							while (!stack.isEmpty()
 									&& OperatorUtils.compare(stack.top(), c)) {
 								rpnList.add(stack.pop());
 							}
 						}
 						// 将当前字符串直接压栈
 						stack.push(c);
 					}
 				}
 
 			}
 		}
 
 		// 如果栈不为空，则将栈中所有元素出栈放到逆波兰链表的最后
 		while (!stack.isEmpty()) {
 			rpnList.add(stack.pop());
 		}
 		return rpnList;
 	}

源码下载地址： http://download.csdn.net/detail/gdutxiaoxu/9375669

参考地址http://blog.csdn.net/luoweifu/article/details/10477447