1、堆栈-Stack
堆栈（也简称作栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。
堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。
Java中已经出了Stack的具体实现类
堆栈的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类类型。
操作集合
（1）入栈push(obj)：把数据元素obj插入堆栈。
（2）出栈pop()：出栈, 删除的数据元素由函数返回。
（3）取栈顶数据元素getTop()：取堆栈当前栈顶的数据元素并由函数返回。
（4）非空否notEmpty()：若堆栈非空则函数返回true，否则函数返回false。
堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。
首先来看应用之一：
中缀表达式转为后缀表达式
1、前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式，而且为了纪念其发明者波兰数学家Jan Lukasiewicz所以前缀表达式也 叫做“波兰表达式”。比如- 1 + 2 3
2、后缀表达式(Postfix Notation)与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -
不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *
3、中缀表达式(Infix Notation)就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算优先级 的括号，比如1-2+3
在中缀表达式的情况下求值，既要考虑括号，优先级，还要考虑操作出现的先后顺序。但是，作为计算机，其计算过程就显的比较复杂，对于一个中缀表达式，需要不停地对表达式进行多次遍历，来查找相应的计算的信息。这样从算法复杂度上来说，是不可取的。前缀表达式和后缀表达式相对于人们常用的中缀表达式最大的不同就在于表达式中的运算符是按照一定的顺序出现（接下来会具体讲解），所以求值过程中并不需要在表达式中使用括号来指定运算顺序，也不需要在计算过程中其中考虑运算符号的优先级。在采用辅助数据结构的情况下，只需要对表达式进行一次遍历即可计算出结果，大大降低了算法复杂度，也更加符合传统计算机的工作方式。
// 采用中缀表达式的算法分析
将中缀表达式转换为后缀表达式：eg:
(1)当读到数字直接送至输出队列中；
(2)当读到运算符t时：
a.将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中；
这句话不好理解，可以说成这样，从栈顶开始，依次弹出比当前处理的运算符优先级高的运算符，直到一个比它优先级低的或者遇到了一个左括号就停止。
b.t进栈；
（3）读到左括号时总是将它压入栈中；
（4）读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号；
（5）中缀表达式全部读完后，若栈中仍有运算符，将其送到输出队列中。
中缀表达式：3+(2-5)*6/3 转换为后缀表达式的过程：
后缀表达式 栈
3
3 +
3 +(
32 +(
32 +(-
325 +(-
325- +
325- +*
325-6 +*
325-6* +/
325-6*3 +/
325-6*3/+
最终后缀表达式为：325-6*3/+
运用后缀表达式进行计算：
(1)建立一个栈S；
(2)从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中；
(3)如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束。
3+(2-5)*6/3=-3 ,其后缀表达式为：325-6*3/+
运算过程如下：
栈 运算
3 2 5 325入栈
3 2-5=-3
3 -3 运算结果进栈
3 -3 6
3 -3*6=-18
3 -18 3 -18/3=-6
3 -6 3+(-6)=-3
-3
//------------------------------------------------------
//直接分析：代码解析都给在了注释里面
1 import java.util.Stack; 2 import java.util.regex.Pattern; 3 4 /** 5 * 将中缀表达式字符串转换为后缀表达式 6 */ 7 public class StringToArithmetic { 8// 默认构造 9public StringToArithmetic() { 10 11} 12 13// 将中缀表达式字符串计算得到结果 14public static double stringToArithmetic(String string) { 15 return suffixToArithmetic(infixToSuffix(string)); 16} 17 18// 将中缀表达式转换为后缀表达式 19public static String infixToSuffix(String exp) { 20 // 创建操作符堆栈 21 Stack<Character> s = new Stack<Character>(); 22 // 要输出的后缀表达式字符串 23 String suffix = ""; 24 int length = exp.length(); // 输入的中缀表达式的长度 25 for (int i = 0; i < length; i++) { 26 char temp;// 临时字符变量 27 // 获取该中缀表达式的每一个字符并进行判断 28 char ch = exp.charAt(i); 29 switch (ch) { 30 // 忽略空格 31 case ' ': 32 break; 33 // 如果是左括号直接压入堆栈 34 case '(': 35 s.push(ch); 36 break; 37 38 // 碰到'+' '-'，将栈中的所有运算符全部弹出去，直至碰到左括号为止，输出到队列中去 39 case '+': 40 case '-': 41 while (s.size() != 0) { 42 temp = s.pop(); 43 if (temp == '(') { 44// 重新将左括号放回堆栈，终止循环 45s.push('('); 46break; 47 } 48 suffix += temp; 49 } 50 // 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈 51 s.push(ch); 52 break; 53 54 // 如果是乘号或者除号，则弹出所有序列，直到碰到加好、减号、左括号为止，最后将该操作符压入堆栈 55 case '*': 56 case '/': 57 while (s.size() != 0) { 58 temp = s.pop(); 59 // 只有比当前优先级高的或者相等的才会弹出到输出队列，遇到加减左括号，直接停止当前循环 60 if (temp == '+' || temp == '-' || temp == '(') { 61s.push(temp); 62break; 63 } else { 64suffix += temp; 65 } 66 } 67 // 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈 68 s.push(ch); 69 break; 70 71 // 如果碰到的是右括号，则距离栈顶的第一个左括号上面的所有运算符弹出栈并抛弃左括号 72 case ')': 73 // 这里假设一定会遇到左括号了，此为自己改进版，已经验证可以过 74 // while ((temp = s.pop()) != '(') { 75 // suffix += temp; 76 // } 77 while (!s.isEmpty()) { 78 temp = s.pop(); 79 if (temp == '(') { 80break; 81 } else { 82suffix += temp; 83 } 84 } 85 break; 86 // 默认情况，如果读取到的是数字，则直接送至输出序列 87 default: 88 suffix += ch; 89 break; 90 } 91 92 } 93 // 如果堆栈不为空，则把剩余运算符一次弹出，送至输出序列 94 while (s.size() != 0) { 95 suffix += s.pop(); 96 } 97 // 98 return suffix; 99}100 101// 将后缀表达式的进行计算得到运算结果 eg:325-6*3/+102public static double suffixToArithmetic(String exp) {103 // 使用正则表达式匹配数字104 Pattern pattern = pile("\\d+||(\\d+\\.\\d+)");105 // 将后缀表达式分割成字符串数组,此处直接使用空白也可以对字符串进行分割！！106 String[] strings = exp.split("");107 Stack<Double> stack = new Stack<Double>();108 for (int i = 0; i < strings.length; i++) {109 // 这里最好是进行判断彻底消除空格，在该数组的第一位为一个隐形的空格，这里一定要注意在使用exp.split("")剔除空白""110 // 由于使用的是""截取导致在数组第一位上面的值为空白111 if (strings[i].equals("")) {112 continue;113 }114 // 如果遇到了数字则直接进栈115 if (pattern.matcher(strings[i]).matches()) {116 stack.push(Double.parseDouble(strings[i]));117 }118 // 如果是运算符，则弹出栈顶的两个数进行计算119 else {120 // ！！！这里需要注意，先弹出的那个数其实是第二个计算数值，这里记作y！121 // 自己书写的时候出错122 double y = stack.pop();123 double x = stack.pop();124 // 将运算结果重新压栈125 stack.push(calculate(x, y, strings[i]));126 }127 }128 // 弹出栈顶元素就是最终结果129 return stack.pop();130}131 132private static Double calculate(double x, double y, String string) {133 // TODO Auto-generated method stub134 // 其实使用case逻辑也可以135 if (string.trim().equals("+")) {136 return x + y;137 }138 if (string.trim().equals("-")) {139 return x - y;140 }141 if (string.trim().equals("*")) {142 return x * y;143 }144 if (string.trim().equals("/")) {145 return x / y;146 }147 return (double) 0;148}149 150 }
1 import java.io.IOException; 2 import java.util.Stack; 3 4 /* 5 * 使用jdk自带stack进行模拟， 6 * 中缀表达式转为后缀表达式 7 */ 8 public class Test { 9public static void main(String[] args) throws Exception {10 // Stack<Character> s = new Stack<Character>();11 //12 // char ch;13 // // 键盘录入一行数据，#号结束录入14 // // 然后压栈15 // while ((ch = (char) (System.in.read())) != '#') {16 // s.push(ch);17 // }18 //19 // // 弹出堆栈20 // while (!s.isEmpty()) {21 // System.out.println(s.pop());22 // }23 24 String str = "3+(2-5)*6/3"; // 后缀表达式为： 325-6*3/+25 String str2 = "3+2-5";26 27 System.out.println(StringToArithmetic.infixToSuffix(str2));28 System.out.println(StringToArithmetic.stringToArithmetic(str2));29 30 // String[] arr = StringToArithmetic.infixToSuffix(str).split("");31 // for (int i = 0; i < arr.length; i++) {32 // if (arr[i].equals("")) {33 // System.out.println(arr[i]);34 // System.out.println("我靠 " + i);35 // }36 // }37 //38 // System.out.println(arr[0]);39}40 }
View Code
