数据结构与算法(三)

在上一篇文章中，我们完整实现了计算器功能，但是还存在一些问题：
解决不支持多位数

不支持多位数的原因就在于：在扫描表达式时，没有考虑多位数的解析。那么思路是：当我们当前的数据是数字的时候，不能直接添加，而是保存到一个String中，需要判断下一位数据是不是字符或者没有下一位，如果是，将字符串转换成int类型数据添加到数栈中，如果不是直接扫描下一位数据继续判断，直到遇到符号或者结尾才结束，将数添加到数栈。当一个数添加到数栈以后，字符串需要重置，否则会出现错误。

在扫描表达式这一步进行修改支持多位数

复制代码

	//当我们遍历的数据是数字的时候
	numCh += ch;//numCh为String类型，我们在遍历循环之前定义
	//判断当前遍历的下一位还是不是数字，如果当前遍历元素是最后一位直接结束
	if(index == express.length() -1){
	numStack.push(Integer.parseInt(numCh));
	}else{
	//当下一个元素是符号的时候才会添加，numCh进行重载，否则数字保存在numCh中
	if(numStack.isOper(express.substring(index+1,index+2).charAt(0))){
	numStack.push(Integer.parseInt(numCh));
	numCh = "";
	}
	}

三种表达式

前缀表达式(波兰表达式)

前缀表达式又称为 波兰表达式，前缀表达式的 运算符位于操作数之前。

例如：(3+4)x5-6 对应的前缀表达式为：- x + 3 4 5 6

注意：前面这个表达式是一个中缀表达式，对应的是后面的这个前缀表达式。它的符号出现的顺序与中缀的顺序不一致。

前缀表达式中的符号顺序，就是他求值的规定了

前缀表达式求值过程

1. 从 右到左 扫描表达式

2. 遇到 数字 时，将数字压入堆栈

3. 遇到 运算符 时

   弹出栈顶的两个数（栈顶和次顶），用运算符对它们做相应的计算，并将结果入栈。

   计算顺序是：先 弹出来的 (运算符) 后 弹出来的

然后重复以上步骤，直到表达式的最左端，最后运算出的值则是表达式的值。

看完前缀表达式的计算逻辑，那么你要明白的是，从一个 中缀表达式 转换为 前缀表达式 时，优先级顺序是已经处理好的，因为在求值时，不进行优先级的判定

例如：(3+4)x5-6 对应的前缀表达式为：- x + 3 4 5 6，前缀表达式求值步骤如下：

1. 从右到左扫描，将 6、5、4、3 压入栈

2. 遇到 + 运算符时：

   将弹出 3 和 4（3 为栈顶元素，4 为次顶元素），计算出 3 + 4 = 7，将结果压入栈

3. 遇到 x 运算符时

   将弹出 7 和 5，计算出 7 x 5 = 35，将 35 压入栈

4. 遇到 - 运算符时

   将弹出 35 和 6，计算出 35 - 6 = 29，压入栈

5. 扫描结束，栈中留下的唯一一个数字 29 则是表达式的值

中缀表达式

中缀表达式就是 常见的运算表达式，如 (3+4)x5-6。

中缀表达式的求值是人类最熟悉的，但是对于计算机来说却不好操作：

• 需要计算运算符的优先级
• 对于中括号来说，笔者想不出实现办法

因此，在计算结果时，往往会将 中缀表达式 转成其他表达式，一般转成后缀表达式。

后缀表达式(逆波兰表达式)

后缀表达式 又称为 逆波兰表达式，与前缀表达式类似，只是 运算符 位于 操作数之后。

比如：(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

再比如：

中缀表达式	后缀表达式
a + b	a b +
a + (b-c)	a b c -
a+(b-c)*d	a b c - d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

后缀表达式求值过程

1. 从 左到右 扫描表达式

2. 遇到 数字 时，将数字压入堆栈

3. 遇到 运算符 时

   弹出栈顶的两个数（栈顶和次顶），用运算符对它们做相应的计算，并将结果入栈。

   计算顺序是：后 弹出来的 (运算符) 先 弹出来的

然后重复以上步骤，直到表达式的最右端，最后运算出的值则是表达式的值。

比如：(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

1. 从左到右扫描，将 3、4 压入堆栈

2. 扫描到 + 运算符时

   将弹出 4 和 3，计算 3 + 4 = 7，将 7 压入栈

3. 将 5 入栈

4. 扫描到 x 运算符时

   将弹出 5 和 7 ，计算 7 x 5 = 35，将 35 入栈

5. 将 6 入栈

6. 扫描到 - 运算符时

   将弹出 6 和 35，计算 35 - 6 = 29，将 29 压入栈

7. 扫描表达式结束，29 是表达式的值

逆波兰计算器

完成一个逆波兰计算器，需求如下：

1. 输入一个 逆波兰表达式，使用栈 Stack（JDK 自带），计算器结果

2. 支持 小括号 和 多位数

   主要这里是讲解数据结构，因此简化为只对整数计算

注意咯：知道逆波兰表达式是什么后，相对来说，实现还是比较容易的，难点其实是在于中缀表达式如何转换为后缀表达式，因为这涉及到运算符的优先级问题。在前面我们实现的时候，其实就是这个运算符优先级问题很刺手。而前缀、后缀表达式里面表达式的优先级在形成表达式时就已经确定了。

复制代码

	public class PolandNotation {
	public static void main(String[] args) {
	//使用逆波兰表达式计算结果
	String suffixExpress = "4 5 * 8 - 60 + 8 2 / +";
	List<String> res = getString(suffixExpress);
	System.out.println("res = " + res);
	int result = 0;
	try {
	result = calculation(res);
	} catch (Exception e) {
	System.out.println(e.getMessage());;
	}
	System.out.println("计算结果为：" + result);
	}
	//将逆波兰表达式转分割，装入ArrayList集合，方便后面进行运算
	public static List<String> getString(String suffix){
	String[] splits = suffix.split(" ");
	List<String> res = new ArrayList<>();
	for(String s: splits){
	res.add(s);
	}
	return res;
	}
	//计算结果
	public static int calculation(List<String> list){
	int result = 0;
	Stack<String> stack = new Stack<>();
	for(String s : list){
	//判断是不是一个数字
	if(s.matches("\\d+")){
	//使用正则表达式判断
	stack.push(s);//入栈
	}else{
	//进行运算
	int num2 = Integer.parseInt(stack.pop());
	int num1 = Integer.parseInt(stack.pop());
	if(s.equals("+")){
	result = num1 + num2;
	}else if(s.equals("-")){
	result = num1 - num2;
	}else if(s.equals("*")){
	result = num1 * num2;
	}else if(s.equals("/")){
	result = num1 / num2;
	}else{
	throw new RuntimeException("运算符错误");
	}
	//将结果入栈
	stack.push(result + "");
	}
	}
	//最后在栈中的就是计算结果
	return Integer.parseInt(stack.pop());
	}
	}

中缀表达式转后缀表达式

通过前面的逆波兰计算器的代码实现，可以看到：后缀表达式对于计算机来说很方便，但是对于人类来说，后缀表达式却不是那么容器写出来的。

中缀表达式转后缀表达式步骤：

1. 初始化两个栈：

   • 运算符栈：s1
   • 中间结果栈：s2

2. 从左到右扫描中缀表达式

3. 遇到操作数时，将其压入 s2

4. 遇到运算符时

   比较 它 与 s1 栈顶运算符的优先级：

   1. 如果 s1 为空，或则栈顶运算符号为 ( ，则将其压入符号栈 s1
   2. 如果：优先级比栈顶运算符 高，也将其压入符号栈 s1
   3. 如果：优先级比栈顶运算符 低 或 相等，将 s1 栈顶的运算符 弹出，并压入到 s2 中

   再重复第 4.1 步骤，与新的栈顶运算符比较（因为 4.3 将 s1 栈顶运算符弹出了）

   这里重复的步骤在实现的时候有点难以理解，下面进行解说：

   1. 如果 s1 栈顶符号 优先级比 当前符号 高或则等于，那么就将其 弹出，压入 s2 中（循环做，是只要 s1 不为空）

      如果栈顶符号为 (，优先级是 -1，就不会弹出，就跳出循环了

   2. 跳出循环后，则将当前符号压入 s1

5. 遇到括号时：

   1. 如果是左括号 ( ：则直接压入 s1

   2. 如果是右括号 )：

      则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃

6. 重复步骤 2 到 5，直到表达式最右端

7. 将 s1 中的运算符依次弹出并压入 s2

8. 依次弹出 s2 中的元素并输出，结果的 逆序 即为：中缀表达式转后缀表达式

下面进行举例说明：

将中缀表达式：1+((2+3)*4)-5 转换为后缀表达式

扫描到的元素	s2 （栈底 -> 栈顶）	s1（栈底 -> 栈顶）	说明
1	1	空	遇到操作数，将其压入 s2
+	1	+	s1 栈为空，将其压入 s1
(	1	+ (	是左括号，压入 s1
(	1	+ ( (	是左括号，压入 s1
2	1 2	+ ( (	遇到操作数，将其压入 s2
+	1 2	+ ( ( +	遇到操作符：与 s1 栈顶运算符比较，为 (，将其压入 s1
3	1 2 3	+ ( ( +	遇到操作数，将其压入 s2
)	1 2 3 +	+ (	遇到右括号：弹出 s1 中的 + 压入 s2 中，这里去掉这一对小括号
*	1 2 3 +	+ ( *	遇到操作符：与 s1 栈顶比较，为 (，将其压入 s1 栈
4	1 2 3 + 4	+ ( *	遇到操作数：将其压入 s2
)	1 2 3 + 4 *	+	遇到右括号：弹出 s 1 中的 * 压入 s2 中，这里去掉这一队小括号
-	1 2 3 + 4 * +	-	遇到操作符：与 s1 栈顶比较，优先级一致，将 s1 中的 + 弹出，并压入 s2 中
5	1 2 3 + 4 * + 5	-	遇到操作数：将其压入 s2
	1 2 3 + 4 * + 5 -	空	解析完毕，将 s1 中的符号弹出并压入 s2 中

由于 s2 是一个栈，弹出是从栈顶弹出，因此逆序后结果就是 1 2 3 + 4 * + 5 -

在学习和使用上有两个层次：

1. 应用层次：别人发明出来的东西，你学习、理解它，并灵活运用它
2. 自创：你自己发明一个东西出来，并使用它

那么这里的中缀转后缀表达式的思路步骤，则属于第一个层次，相关的计算机专家之类的，发明出来了。我们要理解它并灵活运用它。等你能力达到一定层度时，有可能发明出来一个算法。

再比如：绝世武功 -> 降龙十八掌，别人已经创造出来了，你不去学习理解它，如何加以改进并自创？如果没有人教你，你怎么能学会降龙十八掌？

逆波兰表达式计算器代码实现

复制代码

	public class PolandNotation {
	public static void main(String[] args) {
	String str = "1+((2+3)*4)-5";
	List<String> list = toInfixExpressionList(str);
	System.out.println("list = " + list);
	List<String> result = parseSuffixExpressionList(list);
	System.out.println("result:" + result);
	//计算结果
	System.out.println(calculation(result));
	}
	//中缀表达式转后缀表达式
	public static List<String> parseSuffixExpressionList(List<String> list){
	//1.初始化一个栈用来保存符号，直接使用ArrayList来保存中间数据，保存的结果输出就是后缀表达式
	Stack<String> operStack = new Stack<>();
	List<String> result = new ArrayList<String>();
	//2.从左到右遍历中中缀表达式
	for(String c : list){
	if(c.matches("\\d+")){
	//当前表达式是一个数，直接添加到中间数据中
	result.add(c);
	}else{
	//当为符号的情况
	if(operStack.isEmpty()){
	//当符号栈为空的时候，或者遇到“("就直接添加
	operStack.push(c);
	}else if(c.equals("(")){
	operStack.push(c);
	}else if(c.equals(")")){
	//当当前符号为)的时候，弹出栈中数据到中间结果中，直到遇到(就结束
	while(!operStack.peek().equals("(")){
	result.add(operStack.pop());
	}
	//将符号"("弹出
	operStack.pop();
	}else{
	//进行优先级的比较
	while(operStack.size() != 0 && Operational.priority(c) <= Operational.priority(operStack.peek())){
	//当我们要添加的符号的优先级小于或者等于栈顶元素的时候,就将栈顶元素取出加入到中间结果
	result.add(operStack.pop());
	}
	operStack.push(c);//将当前符号加入栈中
	}
	}
	}
	//将符号栈中的符号添加至中间结果
	while(!operStack.isEmpty()){
	result.add(operStack.pop());
	}
	return result;
	}
	//将一个中缀表达式分割并存放到一个ArrayList集合中，方便我们后面转换操作
	public static List<String> toInfixExpressionList(String str){
	List<String> list = new ArrayList<>();
	String s = null;
	int index = 0;//遍历str字符串的索引
	char c;//保存每次遍历的数据
	do{
	c = str.charAt(index);
	s = "";//重置字符串
	//判断这个数据是字符还是数据
	if(c >= 48 && c <= 57){
	//是数字
	s += c;
	//查看下一个是否是数字,注意要防止最后一个元素是多位数，出现索引越界的情况，
	// 所以这里只能判断到length-2就进入循环
	while(index < (str.length()-1) && (str.charAt(index+1) >= 48)
	&& (str.charAt(index+1) <= 57) ){
	//后一个还是数字
	index++;
	s += str.charAt(index);
	}
	list.add(s);
	index++;
	}else{
	//是字符，直接加入
	s += c;
	list.add(s);
	index++;
	}
	}while(index < str.length());
	return list;
	}
	//将逆波兰表达式转分割，装入ArrayList集合，方便后面进行运算
	public static List<String> getString(String suffix){
	String[] splits = suffix.split(" ");
	List<String> res = new ArrayList<>();
	for(String s: splits){
	res.add(s);
	}
	return res;
	}
	//计算结果
	public static int calculation(List<String> list){
	int result = 0;
	Stack<String> stack = new Stack<>();
	for(String s : list){
	//判断是不是一个数字
	if(s.matches("\\d+")){
	//使用正则表达式判断
	stack.push(s);//入栈
	}else{
	//进行运算
	int num2 = Integer.parseInt(stack.pop());
	int num1 = Integer.parseInt(stack.pop());
	if(s.equals("+")){
	result = num1 + num2;
	}else if(s.equals("-")){
	result = num1 - num2;
	}else if(s.equals("*")){
	result = num1 * num2;
	}else if(s.equals("/")){
	result = num1 / num2;
	}else{
	throw new RuntimeException("运算符错误");
	}
	//将结果入栈
	stack.push(result + "");
	}
	}
	//最后在栈中的就是计算结果
	return Integer.parseInt(stack.pop());
	}
	}
	//定义一个工具类，主要用于比较运算符的优先级
	class Operational{
	//定义一个操作符类，用于比较
	private static final int ADD = 1;
	private static final int SUB = 1;
	private static final int MUL = 2;
	private static final int DIV = 2;
	private static final int OPER = 0;
	public static int priority(String c){
	int res = -1;
	switch(c){
	case "+":
	res = ADD;
	break;
	case "-":
	res = SUB;
	break;
	case "*":
	res = MUL;
	break;
	case "/":
	res = DIV;
	break;
	case "(":
	res = OPER;
	break;
	default:
	System.out.println("操作符非法");
	break;
	}
	return res;
	}
	}