栈
栈也是我们常用的数据结构,它先进后出,主要有入栈(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方法会报空指针异常。