记录生活中的点点滴滴

0%

栈也是我们常用的数据结构,它先进后出,主要有入栈(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.push(7);
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;//这些注意位置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;//这些注意位置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) {
// Stack<Double> stack = new Stack<>();
// stack.push((double) 5);
// stack.push((double) 10);
// stack.push(1/(stack.pop()/stack.pop()));
// System.out.println(stack);//[0.5]

System.out.println(getValue("34+5*6-"));//29.0
}

输出结果为29.0

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

具体步骤如下:

  1. 初始化两个栈:运算符栈s1储存中间结果的栈s2

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

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

  4. 遇到运算符时,比较其与s1栈顶运算符的优先级:

    1. 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1;
    3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;
  5. 遇到括号时:

    1. 如果是左括号“(”,则直接压入s1
    2. 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
  6. 重复步骤2至5,直到表达式的最右边

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

  8. 依次弹出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"));//123+4*+5-
System.out.println(switchFun("(3+4)*5-6"));//34+5*6-
}
public static String switchFun(String infix){
//运算符栈s1和存储中间结果的栈s2
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);//如果是数字,压入s2
//如果是 ( 或者 )
else if("(".equals(s)) s1.push(s);
else if(")".equals(s)){
while (!"(".equals(s1.peek())){//peek:返回但不删除栈顶的值
s2.push(s1.pop());
}
s1.pop();//弹出 (
}else {//剩下那么就是运算符号
//当s的优先级小于等于s1栈顶运算符,将s1栈顶的运算符弹出并加入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较
while (s1.size()>0 && Operation.getValue(s1.peek())>=Operation.getValue(s)){
s2.push(s1.pop());
}
s1.push(s);//还要将s压入
}
}
while (s1.size()>0){//将s1中剩余元素依次弹出压入s2
s2.push(s1.pop());
}
//上面已经完成转换,得到的栈s2就是,下面我们将它转换成字符串返回
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方法会报空指针异常。