Java学习-Day8

栈的应用（括号匹配）

一、总述

操作系统的核心数据结构. 准确来说操作系统不过是把硬件提供的功能抽象化了.

这次的代码通过检测括号的匹配来感受栈的实际运用. 尽管如此, 要想体验到操作系统内部栈机制还是有很大差距. 不同 CPU 有不同压栈机制, 在特权级切换时对不同进程的栈也各不相同.

二、任务描述

检查一个字符串的括号是否匹配. 所谓匹配, 是指每个左括号有相应的一个右括号与之对应, 且左括号不可以出现在右括号右边. 可以修改测试字符串, 检查不同情况下的运行. 这里的括号包括 "()" "[]" "{}" 这三种.

三、处理思路

从左至右依次对每个字符扫描, 但是只有遇到括号时才进行处理. 对于其他字符就直接丢弃.

遇到左括号就入栈, 遇到右括号就出栈与之匹配

一旦括号匹配不上就直接输出结果

当然如果匹配完有剩余左括号也不行, 此时可以用一个特殊字符 '#' 来作栈底用来判断是否还有剩余左括号.

四、具体内容

输入

一个字符串表达式, 如下所示 

1
2
3
4
5
6
7
[2 + (1 - 3)] * 4

( )  )

()()(())

({}[])

输出

返回一个布尔值, 匹配成功返回 true , 匹配失败返回 false.

函数代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 *********************
 * Is the bracket matching?
 * 
 * @param paraString The given expression.
 * @return Match or not.
 *********************
 */
public static boolean bracketMatching(String paraString) {
	// Step 1. Initialize the stack through pushing a '#' at the bottom.
	CharStack tempStack = new CharStack();
	tempStack.push('#');
	char tempChar, tempPopedChar;

	// Step 2. Process the string. For a string, length() is a method
	// instead of a member variable.
	for (int i = 0; i < paraString.length(); i++) {
		tempChar = paraString.charAt(i);

		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			tempStack.push(tempChar);
			break;
		case ')':
			tempPopedChar = tempStack.pop();
			if (tempPopedChar != '(') {
				return false;
			} // Of if
			break;
		case ']':
			tempPopedChar = tempStack.pop();
			if (tempPopedChar != '[') {
				return false;
			} // Of if
			break;
		case '}':
			tempPopedChar = tempStack.pop();
			if (tempPopedChar != '{') {
				return false;
			} // Of if
			break;
		default:
			// Do nothing.
		}// Of switch
	} // Of for

	tempPopedChar = tempStack.pop();
	if (tempPopedChar != '#') {
		return false;
	} // Of if

	return true;
}// Of bracketMatching

运行截图

五、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
package datastructure.stack;

/**
 * Char stack. I do not use Stack because it is already defined in Java.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class CharStack {
	/**
	 * The depth.
	 */
	private static final int MAX_DEPTH = 10;

	/**
	 * The actual depth.
	 */
	int depth;

	/**
	 * The data
	 */
	char[] data;

	/**
	 *********************
	 * Construct an empty char stack.
	 *********************
	 */
	public CharStack() {
		depth = 0;
		data = new char[MAX_DEPTH];
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	@Override
	public String toString() {
		String resultString = "";
		for (int i = 0; i < depth; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Push an element.
	 * 
	 * @param paraChar The given char.
	 * @return Success or not.
	 *********************
	 */
	public boolean push(char paraChar) {
		if (depth == MAX_DEPTH) {
			System.out.println("Stack full.");
			return false;
		} // Of if

		data[depth] = paraChar;
		depth++;

		return true;
	}// Of push

	/**
	 *********************
	 * Pop an element.
	 * 
	 * @return The popped char.
	 *********************
	 */
	public char pop() {
		if (depth == 0) {
			System.out.println("Nothing to pop.");
			return '\0';
		} // Of if

		char resultChar = data[depth - 1];
		depth--;

		return resultChar;
	}// Of pop

	/**
	 *********************
	 * Is the bracket matching?
	 * 
	 * @param paraString The given expression.
	 * @return Match or not.
	 *********************
	 */
	public static boolean bracketMatching(String paraString) {
		// Step 1. Initialize the stack through pushing a '#' at the bottom.
		CharStack tempStack = new CharStack();
		tempStack.push('#');
		char tempChar, tempPopedChar;

		// Step 2. Process the string. For a string, length() is a method
		// instead of a member variable.
		for (int i = 0; i < paraString.length(); i++) {
			tempChar = paraString.charAt(i);

			switch (tempChar) {
			case '(':
			case '[':
			case '{':
				tempStack.push(tempChar);
				break;
			case ')':
				tempPopedChar = tempStack.pop();
				if (tempPopedChar != '(') {
					return false;
				} // Of if
				break;
			case ']':
				tempPopedChar = tempStack.pop();
				if (tempPopedChar != '[') {
					return false;
				} // Of if
				break;
			case '}':
				tempPopedChar = tempStack.pop();
				if (tempPopedChar != '{') {
					return false;
				} // Of if
				break;
			default:
				// Do nothing.
			}// Of switch
		} // Of for

		tempPopedChar = tempStack.pop();
		if (tempPopedChar != '#') {
			return false;
		} // Of if

		return true;
	}// Of bracketMatching

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CharStack tempStack = new CharStack();

		for (char ch = 'a'; ch < 'm'; ch++) {
			tempStack.push(ch);
			System.out.println("The current stack is: " + tempStack);
		} // Of for i

		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = tempStack.pop();
			System.out.println("Poped: " + tempChar);
			System.out.println("The current stack is: " + tempStack);
		} // Of for i

		boolean tempMatch;
		String tempExpression = "[2 + (1 - 3)] * 4";
		tempMatch = bracketMatching(tempExpression);
		System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "( )  )";
		tempMatch = bracketMatching(tempExpression);
		System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "()()(())";
		tempMatch = bracketMatching(tempExpression);
		System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "({}[])";
		tempMatch = bracketMatching(tempExpression);
		System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = ")(";
		tempMatch = bracketMatching(tempExpression);
		System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

	}// Of main
}// Of CharStack

递归

一、总述

用两个例子来介绍递归, 一个是求整数和 sumToN , 另一个则是非常经典的斐波那契数列.

递归从大角度看就是得出结果的最后一步, 但这毕竟是函数不是一个确定的值, 所以我们需要做的就是将大步骤化成有一个确定数值的小步骤.

这么看来递归就是一个出口的确切数值加上最后一步的表达式.

二、思考

对于 sumToN 来说, 出口值就是0, 表达式是 $ sumToN(paraN - 1) + paraN $.

对于斐波那契数列, 出口值为1, 表达式是 $ fibonacci(paraN - 1) + fibonacci(paraN - 2) $

当然在函数中还需要处理非法输入.

三、具体内容

函数名

sumToN(int paraN)

输入

一个整数

输出

1 至该输入的所有整数之和

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *********************
 * Sum to N. No loop, however a stack is used.
 * 
 * @param paraN The given value.
 * @return The sum.
 *********************
 */
public static int sumToN(int paraN) {
	if (paraN <= 0) {
		// Basis.
		return 0;
	} // Of if

	return sumToN(paraN - 1) + paraN;
}// Of sumToN

函数名

fibonacci(int paraN)

输入

一个整数, 代表数列中第几位

输出

数列中输入整数位的数值

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 *********************
 * Fibonacci sequence.
 * 
 * @param paraN The given value.
 * @return The sum.
 *********************
 */
public static int fibonacci(int paraN) {
	if (paraN <= 0) {
		// Negative values are invalid. Index 0 corresponds to the first element 0.
		return 0;
	}
	if (paraN == 1) {
		// Basis.
		return 1;
	} // Of if

	return fibonacci(paraN - 1) + fibonacci(paraN - 2);
}// Of fibonacci

运行截图

改进算法

上面的解法无非是常规套路, 在求斐波那契数列高位的时候就会出现非常耗时的情况, 甚至会出现栈溢出的错误. 这是因为在递归过程中它的次数是以指数级别增长.

为了体现递归的思想这里我采用尾递归的方式, 实际上简化为了一般函数的调用过程.

函数名

fibonacci_new(int paraN, int paraPre, int paraCur)

输入

三个整数分别为数列第几位, 数列前一个数的值, 数列当前数的值

输出

数列中输入整数位的数值

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 *********************
 * Fibonacci sequence.Tail recursion
 * 
 * @param paraN   The given value.
 * @param paraPre The previous value in fibonacci sequence.
 * @param paraCur The current value in fibonacci sequence.
 * @return The sum.
 *********************
 */
public static int fibonacci_new(int paraN, int paraPre, int paraCur) {
	if (paraN <= 0) {
		// Negative values are invalid. Index 0 corresponds to the first element 0.
		return 0;
	}
	if (paraN == 1) {
		// Basis.
		return paraCur;
	} // Of if

	return fibonacci_new(paraN - 1, paraCur, paraPre + paraCur);
}// Of fibonacci_new

对比图

四、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package datastructure;

/**
 * Recursion. A method can (directly or indirectly) invoke itself. The system
 * automatically creates a stack for it.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class Recursion {
	/**
	 *********************
	 * Sum to N. No loop, however a stack is used.
	 * 
	 * @param paraN The given value.
	 * @return The sum.
	 *********************
	 */
	public static int sumToN(int paraN) {
		if (paraN <= 0) {
			// Basis.
			return 0;
		} // Of if

		return sumToN(paraN - 1) + paraN;
	}// Of sumToN

	/**
	 *********************
	 * Fibonacci sequence.
	 * 
	 * @param paraN The given value.
	 * @return The sum.
	 *********************
	 */
	public static int fibonacci(int paraN) {
		if (paraN <= 0) {
			// Negative values are invalid. Index 0 corresponds to the first element 0.
			return 0;
		}
		if (paraN == 1) {
			// Basis.
			return 1;
		} // Of if

		return fibonacci(paraN - 1) + fibonacci(paraN - 2);
	}// Of fibonacci

	/**
	 *********************
	 * Fibonacci sequence.Tail recursion
	 * 
	 * @param paraN   The given value.
	 * @param paraPre The previous value in fibonacci sequence.
	 * @param paraCur The current value in fibonacci sequence.
	 * @return The sum.
	 *********************
	 */
	public static int fibonacci_new(int paraN, int paraPre, int paraCur) {
		if (paraN <= 0) {
			// Negative values are invalid. Index 0 corresponds to the first element 0.
			return 0;
		}
		if (paraN == 1) {
			// Basis.
			return paraCur;
		} // Of if

		return fibonacci_new(paraN - 1, paraCur, paraPre + paraCur);
	}// Of fibonacci_new

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int tempValue = 5;
		System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));
		tempValue = -1;
		System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < 40; i++) {
			System.out.println("Fibonacci " + i + ": " + fibonacci(i));
//			System.out.println("Fibonacci_new " + i + ": " + fibonacci_new(i, 0, 1));
		} // Of for i
		long endTime = System.currentTimeMillis();
		System.out.println("Execute time is: " + (endTime - startTime) + " ms");
	}// Of main
}// Of class Recursion

总结

无论是括号匹配还是递归代码, 一定都是先有思路然后再进行雕琢. 思考的过程不能少, 不能拿到需求就直接 main 和 print.

其次是斐波那契数列, 除了尾递归的方法还有用数组存储进行递推操作. 要是数学功底好还可以用矩阵快速幂进行计算. 不过这些离递归思想太远, 在这里就不细说了.