栈
栈也是我们常用的数据结构，它先进后出，主要有入栈（push）和出栈（pop）两种方法。
数组模拟栈
我们接下来用数组去模拟栈，它的成员变量有maxSize（栈的大小）、arr（数组模拟栈）、top=-1（头指针）。
构造方法中传入栈的大小，赋值给maxSize，并根据它初始化arr。类中还有其他常用方法：
直接上代码，不难理解：
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
| class ArrayStack{
private int maxSize;
private int[] arr;
private int top = -1;
public ArrayStack(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
}
public boolean isFull(){
return top==this.maxSize-1;
}
public boolean isEmpty(){
return top==-1;
}
public void push(int val){
if(!isFull()){
arr[++top] = val;
}else {
throw new RuntimeException("栈已满，入栈失败");
}
}
public int pop(){
if(!isEmpty()){
return arr[--top];
}else {
throw new RuntimeException("栈为空，出栈失败...");
}
}
public void list(){
int i = top;
while (i>-1){
System.out.printf("%d ",arr[i--]);
}
System.out.println();
}
}
|
main方法中进行测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void main(String[] args) {
ArrayStack stack = new ArrayStack(6);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.list();
stack.pop();
stack.pop();
stack.list();
}
|
输出结果如下：
运算表达式求值
我们用计算器常常会输入一段表达式，它会返回结果。例如 9+1+(1+2)*(3+4) ，结果是31。
我们可以借助栈这一数据结构实现这一过程，写一个函数，传入表达式参数，返回结果。
为了简单起见，我们只支持一位数，然后只支持加减乘除四种运算，当然可以有括号。
主要的思想是：
代码如下：
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
| public static double calc(String expression){
Stack<Double> numStack = new Stack<>();
Stack<Character> signalStack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char s = expression.charAt(i);
if(s=='(') ;
else if(s=='+') signalStack.push(s);
else if(s=='-') signalStack.push(s);
else if(s=='*') signalStack.push(s);
else if(s=='/') signalStack.push(s);
else if(s==')'){
char op = signalStack.pop();
double v = numStack.pop();
if(op=='+') v=numStack.pop()+v;
else if(op=='-') v=numStack.pop()-v;
else if(op=='*') v=numStack.pop()*v;
else if(op=='/') v=numStack.pop()/v;
numStack.push(v);
}else {
numStack.push(Double.parseDouble(String.valueOf(s)));
}
}
while (true){
if(signalStack.isEmpty()){
break;
}
Double v = numStack.pop();
char op = signalStack.pop();
if(op=='+') v=numStack.pop()+v;
else if(op=='-') v=numStack.pop()-v;
else if(op=='*') v=numStack.pop()*v;
else if(op=='/') v=numStack.pop()/v;
numStack.push(v);
}
return numStack.pop();
}
|
main方法中调用它：
1
2
3
| public static void main(String[] args) {
System.out.println(calc("9+1+(1+2)*(3+4)"));
}
|
得到的结果是31.0
逆波兰表达式求值
逆波兰表达式又叫做后缀表达式，一个运算表达式，如：(3+4)*5-6，我们转成后缀表达式就是：34+5*6-
我们设定一个函数，参数为给定我们的一个逆波兰表达式，返回这个逆波兰表达式的值。
其实比上面那个要简单多了，我们只要遍历一遍，数字入栈，符号进行运算再入栈，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static double getValue(String suffix){
Stack<Double> stack = new Stack<>();
for (int i = 0; i < suffix.length(); i++) {
char s = suffix.charAt(i);
if(s=='+') stack.push(stack.pop()+stack.pop());
else if(s=='-') stack.push(-stack.pop()+stack.pop());
else if(s=='*') stack.push(stack.pop()*stack.pop());
else if(s=='/') stack.push(1/(stack.pop()/stack.pop()));
else {
stack.push(Double.parseDouble(String.valueOf(s)));
}
}
return stack.pop();
}
|
main方法中进行测试：
1
2
3
4
5
6
7
8
9
| public static void main(String[] args) {
System.out.println(getValue("34+5*6-"));
}
|
输出结果为29.0
中缀表达式转换为后缀表达式
具体步骤如下：
初始化两个栈：运算符栈s1和储存中间结果的栈s2；
从左至右扫描中缀表达式；
遇到操作数时，将其压入s2；
遇到运算符时，比较其与s1栈顶运算符的优先级：
- 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
遇到括号时：
- 如果是左括号“(”，则直接压入s1
- 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
重复步骤2至5，直到表达式的最右边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
举例：中缀表达式为：1+((2+3)×4)-5 转换成后缀表达式为：123+4*+5- 过程如下：
代码实现如下：
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
|
public class SwitchDemo {
public static void main(String[] args) {
System.out.println(switchFun("1+((2+3)*4)-5"));
System.out.println(switchFun("(3+4)*5-6"));
}
public static String switchFun(String infix){
Stack<String> s1 = new Stack<>();
Stack<String> s2 = new Stack<>();
for (int i = 0; i < infix.length(); i++) {
String s = String.valueOf(infix.charAt(i));
if(Character.isDigit(s.charAt(0))) s2.push(s);
else if("(".equals(s)) s1.push(s);
else if(")".equals(s)){
while (!"(".equals(s1.peek())){
s2.push(s1.pop());
}
s1.pop();
}else {
while (s1.size()>0 && Operation.getValue(s1.peek())>=Operation.getValue(s)){
s2.push(s1.pop());
}
s1.push(s);
}
}
while (s1.size()>0){
s2.push(s1.pop());
}
StringBuilder sb = new StringBuilder();
s2.forEach(x-> sb.append(x));
return String.valueOf(sb);
}
}
class Operation{
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
private static int LEF = 0;
public static int getValue(String op){
int res = 0;
switch (op){
case "+":
res = ADD;
break;
case "-":
res = SUB;
break;
case "*":
res = MUL;
break;
case "/":
res = DIV;
break;
case "(":
res = LEF;
break;
default:
System.out.println("不存在该运算符");
break;
}
return res;
}
}
|
中间我在比较字符串s和 "(" 或者 ")" 的时候，如果用 == 去比较的话会出现错误。
因为字符串s是我们new出来的，不是放在字符串常量池中的，所以它们不相等。我们要用 equals 方法区比较。
举个例子：
1
| System.out.println(new String("(") == "(");
|
执行的话会返回 false，而不是 true
1
| System.out.println(new String("(").equals("("));
|
这一句会返回 true，用 equals 方法比较不会返回false。
还有一点，我们比较的时候尽量把 "xxxx"这些放在 equals 函数的前面，把字符串变量放在括号内。
因为如果字符串变量为 null 的话，还调用它的equals方法会报空指针异常。