栈是限制插入和删除只能在一个位置上进行的 List,该位置是 List 的末端,叫做栈的顶(top),对于栈的基本操作有 push 和 pop,前者是插入,后者是删除。

栈也是 FIFO 表。

栈的实现有两种,一种是使用数组,一种是使用链表。

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
public class MyArrayStack<E> {

private ArrayList<E> list = new ArrayList<>();

public void push(E e) {
list.add(e);
}

public E pop() {
return list.remove(list.size() - 1);
}

public E peek() {
return list.get(list.size() - 1);
}

public boolean isEmpty() {
return list.size() == 0;
}
}

public class MyLinkStack<E> {

LinkedList<E> list = new LinkedList<>();

public void push(E e) {
list.addLast(e);
}

public E pop() {
return list.removeLast();
}

public E peek() {
return list.getLast();
}

public boolean isEmpty() {
return list.size() == 0;
}
}

栈的应用

平衡符号

给定一串代码,我们检查这段代码当中的括号是否符合语法。

例如:[{()}] 这样是合法的,但是 [{]}() 就是不合法的。

如下是测试代码:

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
public class BalanceSymbol {

public boolean isBalance(String string) {
MyArrayStack<Character> stack = new MyArrayStack<>();
char[] array = string.toCharArray();
for (char ch : array) {
if ("{[(".indexOf(ch) >= 0) {
stack.push(ch);
} else if ("}])".indexOf(ch) >= 0) {
if (isMatching(stack.peek(), ch)) {
stack.pop();
}
}
}

return stack.isEmpty();
}

private boolean isMatching(char peek, char ch) {
if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) {
return true;
}
return false;
}

public static void main(String[] args) {
BalanceSymbol symbol = new BalanceSymbol();
String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}";
String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]";
System.out.println(symbol.isBalance(string));
System.out.println(symbol.isBalance(string2));
}
}

后缀表达式

例如一个如下输入,算出相应的结果,

3 + 2 + 3 * 2 = ?

这个在计算顺序上不同会产生不同的结果,如果从左到右计算结果是 16,如果按照数学优先级计算结果是 11。

如果把上述的中缀表达式转换成后缀表达式:

3 2 + 3 2 * +

如果使用后缀表达式来计算这个表达式的值就会非常简单,只需要使用一个栈。

每当遇到数字的时候,把数字入栈。

每当遇到操作符,弹出2个元素根据操作符计算后,入栈。

最终弹出栈的唯一元素就是计算结果。

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

/**
* 简化版本,每个操作数只一位,并且假设字符串合法
*/
public class PostfixExpression {

public static int calculate(String string) {
MyArrayStack<String> stack = new MyArrayStack<>();

char[] arr = string.toCharArray();

for (char ch : arr) {
if ("0123456789".indexOf(ch) >= 0) {
stack.push(ch + "");
} else if ("+-*/".indexOf(ch) >= 0) {
int a = Integer.parseInt(stack.pop());
int b = Integer.parseInt(stack.pop());
if (ch == '+') {
stack.push((a + b) + "");
} else if (ch == '-') {
stack.push((a - b) + "");
} else if (ch == '*') {
stack.push((a * b) + "");
} else if (ch == '/') {
stack.push((a / b) + "");
}
}
}
return Integer.parseInt(stack.peek());
}

public static void main(String[] args) {
System.out.println(calculate("32+32*+"));
}
}

中缀表达式转换成后缀表达式

假设只运行 +,-,*,/,() 这几种表达式。并且表达式合法。

a + b * c - (d * e + f) / g 转换后的后缀表达式如下:

a b c * + d e * f + g / -

使用栈中缀转后缀步骤如下:

  • 当读到操作数立即把它输出

  • 如果遇到操作符入栈,如果遇到的左括号也放到栈中

  • 如果遇到右括号,就开始弹出栈元素,直到遇到对应的左括号,左括号只弹出不输出。

  • 如果遇到其他符号,那么从栈中弹出栈元素知道发现优先级更低的元素为止。

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
import java.util.HashMap;
import java.util.Map;

public class ExpressionSwitch {

private static Map<Character, Integer> map = new HashMap<Character, Integer>();

static {
map.put('+', 0);
map.put('-', 1);
map.put('*', 2);
map.put('/', 3);
map.put('(', 4);
}

private static char[][] priority = {
// 当前操作符
// + - * / (
/* 栈 + */{ '>', '>', '<', '<', '<'},
/* 顶 - */{ '>', '>', '<', '<', '<'},
/* 操 * */{ '>', '>', '>', '>', '<'},
/* 作 / */{ '>', '>', '>', '>', '<'},
/* 符 ( */{ '<', '<', '<', '<', '<'},
};

public static String switch1(String string) {
StringBuilder builder = new StringBuilder();

char[] arr = string.toCharArray();

MyArrayStack<Character> stack = new MyArrayStack<>();
for (char ch : arr) {
if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) {
builder.append(ch);
} else if ('(' == ch) {
stack.push(ch);
} else if (')' == ch) {
while (true && !stack.isEmpty()) {
char tmp = stack.pop();
if (tmp == '(') {
break;
} else {
builder.append(tmp);
}
}
} else {
while (true) {
if (stack.isEmpty()) {
stack.push(ch);
break;
}
char tmp = stack.peek();
if (isPriorityHigh(tmp, ch)) {
builder.append(stack.pop());
} else {
stack.push(ch);
break;
}
}
}
}

while(!stack.isEmpty()) {
builder.append(stack.pop());
}

return builder.toString();
}

private static boolean isPriorityHigh(char tmp, char ch) {
return priority[map.get(tmp)][map.get(ch)] == '>';
}

public static void main(String[] args) {
System.out.println(switch1("a+b*c-(d*e+f)/g"));
}
}

—EOF—