3. 4.栈

3.1. 4.1.栈的介绍

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

3.2. 4.2.入栈图解

_images/4.2_11.png

3.3. 4.3.出栈图解

_images/4.3_11.png

3.4. 4.4.代码实现

/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: ArrayStack.java
* @Package com.tuling.infix
* @Description:
* @author 北京图灵学院
* @date 2019年11月21日
* @version V1.0
*/

package com.tuling.infix;

/**
 * @ClassName: ArrayStack
 * @Description:
 * @author 小白
 * @date 2019年11月21日
 *
 */

public class ArrayStack {

    private int[] stack;
    private int count;
    private int top;

    /**
     * 创建一个新的实例 ArrayStack.
     *
     */
    public ArrayStack() {
        this(10);
    }

    /**
     * 创建一个新的实例 ArrayStack.
     *
     * @param count
     */
    public ArrayStack(int count) {
        this.count = count;
        stack = new int[count];
        top = -1;
    }

    /**
    *
    * @Title: push
    * @Description:入栈
    * @param data
    * @return void
    * @throws
    */
    public void push(int data) {
        if(isFull()) {
            throw new IllegalArgumentException("栈溢出！");
        }

        stack[++top] = data;

    }

    /**
    *
    * @Title: show
    * @Description:显示栈内的所有数据
    * @param
    * @return void
    * @throws
    */
    public void show() {
        if(isEmpty()) {
            throw new IllegalArgumentException("栈为空！");
        }

        //从栈顶开始展示
        for(int i = top; i >= 0; i--) {
            System.out.print(stack[i] + "  ");
        }
        System.out.println();
    }

    /**
    *
    * @Title: pop
    * @Description:弹栈
    * @param
    * @return int
    * @throws
    */
    public int pop() {
        if(isEmpty()) {
            throw new IllegalArgumentException("栈为空！");
        }

        return stack[top--];
    }

    /**
    *
    * @Title: isFull
    * @Description:判断栈是否已满
    * @param
    * @return boolean
    * @throws
    */
    public boolean isFull() {
        return top == (count-1);
    }

    /**
    *
    * @Title: isEmpty
    * @Description:判断栈是否为空
    * @param
    * @return boolean
    * @throws
    */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * @return stack
     */
    public int[] getStack() {
        return stack;
    }

    /**
     * @param stack the stack to set
     */
    public void setStack(int[] stack) {
        this.stack = stack;
    }

    /**
     * @return count
     */
    public int getCount() {
        return count;
    }

    /**
     * @param count the count to set
     */
    public void setCount(int count) {
        this.count = count;
    }

    /**
     * @return top
     */
    public int getTop() {
        return top;
    }

    /**
     * @param top the top to set
     */
    public void setTop(int top) {
        this.top = top;
    }

}

测试
/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: StackDemo.java
* @Package com.tuling.infix
* @Description:
* @author 北京图灵学院
* @date 2019年11月21日
* @version V1.0
*/

package com.tuling.infix;


/**
* @ClassName: StackDemo
* @Description:
* @author 小白
* @date 2019年11月21日
*
*/

public class StackDemo {

    /**
    * @Title: main
    * @Description:
    * @param @param args
    * @return void
    * @throws
    */

    public static void main(String[] args) {
        ArrayStack as = new ArrayStack(5);
        //压栈
        as.push(4);
        as.push(26);
        as.push(8);
        as.push(30);
        as.push(10);
//      as.push(2);
        //打印栈内数据
        as.show();
        System.out.println("-----------弹栈操作--------------");
        //弹栈
        System.out.println(as.pop() + " 弹栈");
        as.show();

        System.out.println(as.pop() + " 弹栈");
        as.show();

    }

}

运行结果：

_images/result5.png

3.5. 4.5.使用栈实现中缀表达式计算器

3.5.1. 4.5.1.计算器实现原理分析

  1. 准备工作：
    1. 一个用来存储数值的数值栈：numStack
    2. 一个用来存储运算符的运算符栈：operStack
  2. 将字符串表达式拆分，然后逐个扫描。
    1. 如果是数字，直接压入数值栈
    2. 如果是运算符
      1. 如果当前运算符栈为空，直接将运算符压入运算符栈
      2. 如果运算符不为空
        1. 如果当前运算符的优先级高于运算符栈栈顶的运算符，则直接压入运算符栈
        2. 如果当前运算符的优先级小于或等于运算符栈栈顶的运算符，则需要将栈顶的运算符弹出，同时需要从数值栈中弹出两个数，与栈顶运算与进行运算，然后将运算结果重新压入数值栈。最后继续判断当前运算符与栈顶运算符的优先级，重复该步骤。
  3. 表达式扫描完成后，如果运算符栈不为空，则弹出栈顶运算符，同时弹出数值栈中的两个数，进行运算，将结果重新压入数值栈，直到运算符栈为空，此时数值栈中的最后一个数值即为表达式的运算结果。

3.5.2. 4.5.2.表达式入栈原理图解

表达式为：2x3x2+4-5-6x2，首先将表达式拆分为 “2”，“x”，“3”，“x”，“2”，“+”，“4”，“-”，“5”，“-”，“6”，“x”，“2” 1.扫描第一个字符串，判断为数字 “2”，直接压入数值栈

_images/18.jpg

2.扫描第二个字符串，判断为运算符“*”，运算符栈为空，直接压入运算符栈

_images/22.jpg

3.扫描第三个字符串，判断为数字“3”，直接压入数值栈

_images/31.jpg

4.扫描第四个字符串，判断为运算符“*”，运算符栈不为空，与栈顶的运算符 * 优先级相等，需要进行运算 1. 首先弹出运算符栈栈顶的 * 2. 弹出数值栈中的 3 3. 弹出数值栈中的 2 4. 将 3 * 2 的结果重新压入数值栈 5.

_images/41.jpg

将第四个字符串的*压入运算符栈

5.扫描第五个字符串，判断为数值“2”，直接压入数值栈

_images/51.jpg

6.扫描第六个字符串，判断为运算符 “+”，继续与运算符栈顶进行优先级比较。结果为小于 1. 首先弹出运算符栈栈顶的 * 2. 弹出数值栈中的 2 3. 弹出数值栈中的 6 4. 将 2 * 6 的结果重新压入数值栈 5. 将第六个字符串的+压入运算符栈

_images/61.jpg

7.扫描第七个字符串，判断为数值“4”，直接入数值栈

_images/71.jpg

8.扫描第八个字符串，判断为运算符 “-”，继续与运算符栈顶进行优先级比较。结果为等于

_images/81.jpg

9.扫描第九个字符串，判断为数值“5”，直接入数值栈

_images/91.jpg

10.扫描第十个字符串，判断为运算符 “-”，继续与运算符栈顶进行优先级比较。结果为等于 1. 首先弹出运算符栈栈顶的 - 2. 弹出数值栈中的 5 3. 弹出数值栈中的 16 4. 将 16 - 5 的结果重新压入数值栈 5. 将第十个字符串的-压入运算符栈

_images/101.jpg

11.扫描第十一个字符串，判断为数值“6”，直接入数值栈

_images/111.jpg

12.扫描第十二个字符串，判断为运算符 “*”，继续与运算符栈顶进行优先级比较。结果为大于

_images/121.jpg

13.扫描第十三个字符串，判断为数值“2”，直接入数值栈

_images/131.jpg

4.5.3.表达式解析入栈过程

4.5.4.计算过程图解 表达式为：2*3*2+4-5-6*2，解析完成后，栈内情况如下图所示

_images/4.2.11.jpg

重复如下步骤，直到运算符栈为空： 1. 从 operStack 栈弹出一个运算符 2. 从numStack 栈弹出两个数据 3. 计算结果后将结果重新压入数值栈

4.5.5.中缀表达式计算器代码实现

/**
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title:  MyCalculator.java
 * @Package com.tuling.calculator
 * @Description:
 * @author: 小白
 * @Date 2019年12月3日 下午3:28:03
 * @version V1.0
 * @Copyright:
 */
package com.tuling.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @ClassName MyCalculator
 * @Description 中缀表达式实现计算器
 * @Author 北京图灵学院
 * @Date 2019年12月3日 下午3:28:03
 */
public class MyCalculator {

    //数值栈
    private MyStack numStack;
    //运算符栈
    private MyStack operStack;

    //ArrayList 用来存放表达式拆分后的字符串
    private List<String> sourceExp;

    /**
     * @Title:  MyCalculator
     * @Description:
     * @param:
     * @throws
     */
    public MyCalculator() {
        numStack = new MyStack(10);
        operStack = new MyStack(10);
        sourceExp = new ArrayList<String>();
    }

    /**
     *
     * @Title: calculate
     * @Description:计算
     * @param: @param expression
     * @param: @return
     * @return: int
     * @throws
     */
    public int calculate(String expression) {
        //先将原始表达式拆分
        getExp(expression);

        //将原始表达式逐个解析，入栈
        inStack(sourceExp);

        //入栈完成，依次从运算符栈弹出一个运算符，从数值栈弹出两个数，进行运算。
        while(!operStack.isEmpty()) {
            //弹出当前运算符栈顶的运算符
            String oper = operStack.pop();
            String num1 = numStack.pop();
            String num2 = numStack.pop();

            //计算结果
            int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);

            //将结果压入数值栈
            numStack.push(result+"");
        }
        //将数值栈的数返回。
        return Integer.parseInt(numStack.pop());
    }

    /**
     * @param list
     * @Title: inStack
     * @Description:将原始表达式逐个解析，进行入栈操作
     *  遍历集合，拿到每一个元素并且判断
     *      1.如果是运算符
     *          1.1> 如果当前运算符栈不为空：
     *              1.1.1> 如果当前运算符的优先级小于或者等于栈顶的运算符优先级
     *                      从数值栈中弹出两个数，并且将运算的结果压入数值栈
     *                      将运算符压入运算符栈
     *              1.1.2> 否则：直接压入运算符栈
     *          1.2> 如果当前运算符栈为空：直接压入运算符栈
     *      2.如果是数值：
     *          直接压入数值栈
     * @param:
     * @return: void
     * @throws
     */
    private void inStack(List<String> list) {
        for(String str:list) {
            if(isOper(str)) {
                //判断
                if(operStack.isEmpty()) {
                    //运算符栈为空，直接入栈
                    operStack.push(str);
                }else {
                    //不为空，需要与栈顶运算符比较优先级高低
                    //如果当前运算符的优先级小于或等于运算符栈顶的优先级，需要运算
                    if(priority(str) <= priority(operStack.peek())) {
                        //需要运算，
                        //弹出当前运算符栈顶的运算符
                        String oper = operStack.pop();
                        String num1 = numStack.pop();
                        String num2 = numStack.pop();

                        //计算结果
                        int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);

                        //将结果压入数值栈
                        numStack.push(result+"");

                        //将运算符压入运算符栈
                        operStack.push(str);

                    }else if(priority(str) > priority(operStack.peek())) {
                        //直接入运算符栈
                        operStack.push(str);
                    }
                }
            }else if(isNum(str)) {
                //数字，直接入数值栈
                numStack.push(str);
            }
        }
    }

    public int cal(int num1,int num2,String oper) {
        int result = 0;
        switch (oper) {
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num2 - num1;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }

    /**
     *
     * @Title: priority
     * @Description:返回运算符的优先级
     * @param: @param oper
     * @param: @return
     * @return: int
     * @throws
     */
    public int priority(String oper) {
        switch (oper) {
            case "*":
            case "/":
                return 2;
            case "+":
            case "-":
                return 1;
        default:
            return 0;
        }
    }

    /**
     * @Title: isNum
     * @Description:判断是否为数字
     * @param: @param str
     * @param: @return
     * @return: boolean
     * @throws
     */
    private boolean isNum(String str) {
        return str.matches("[0-9]+");
    }

    /**
     * @Title: isOper
     * @Description:判断是否为运算符
     * @param: @param str
     * @param: @return
     * @return: boolean
     * @throws
     */
    private boolean isOper(String str) {
        return str.matches("[\\+\\-\\*\\/]");
    }

    /**
     * @Title: getExp
     * @Description:将原始表达式拆分为字符串
     * @param: @param expression
     * @return: void
     * @throws
     */
    private void getExp(String expression) {
        StringTokenizer stringTokenizer = new StringTokenizer(expression, "+-*/", true);
        while(stringTokenizer.hasMoreTokens()) {
            sourceExp.add(stringTokenizer.nextToken());
        }
    }
}

测试类代码如下：

/**
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title:  Test.java
 * @Package com.tuling.calculator
 * @Description:
 * @author: 小白
 * @Date 2019年12月3日 下午7:28:33
 * @version V1.0
 * @Copyright:
 */
package com.tuling.calculator;

/**
 * @ClassName Test
 * @Description
 * @Author 北京图灵学院
 * @Date 2019年12月3日 下午7:28:33
 */
public class Test {

    /**
     * @Title: main
     * @Description:
     * @param: @param args
     * @return: void
     * @throws
     */
    public static void main(String[] args) {
//      String expression = "2+3*4";
        String expression = "2*3*4+5-6-4*2";

        MyCalculator mc = new MyCalculator();
        int result = mc.calculate(expression);
        System.out.println("表达式：" + expression + " = " + result);
    }

}

4.6.逆波兰表达式 逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

举个栗子，将通常的中缀表达式转换成逆波兰表达式：

中缀表达式 逆波兰计法
5+6 56+
2*3-6 23*6-
（1+2）*（3+4） 12+34+*

3.5.3. 4.6.1.中缀表达式转后缀表达式

算法实现： 首先需要准备一个作为临时存储运算符的栈operStack，一个作为输入逆波兰式的集合postFixList，逐序进行如下步骤：

  1. 若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入postFixList

2. 若取出的字符是运算符，则将该运算符与operStack栈栈顶元素比较，如果该运算符优先级(不包括括号运算符)大于operStack栈栈顶运算符优先级，则将该运算符进operStack栈，否则，将operStack栈的栈顶运算符弹出，送入postFixList 中，直至operStack栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入operStack栈。

  1. 若取出的字符是“（”，则直接送入operStack栈顶。

4. 若取出的字符是“）”，则将距离operStack栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入postFixList ，此时抛弃“（”。

  1. 重复上面的1~4步，直至处理完所有的输入字符

3.5.4. 4.6.2.中缀转后缀原理图解

还是举个栗子，就以( 1 + 2 ) * ( 3 + 4 )为栗，当算式转换成1 2 + 3 4 +*后，运算过程如下：

1.读取到运算符开圆括号“（”，直接入符号栈（入栈后，优先级最弱）

_images/4.3.13.jpg

2.读取到数值1，直接加入逆波兰表达式的集合

_images/4.3.21.jpg

3.读取到运算符“+”，栈顶为（，+直接入符号栈

_images/4.3.31.jpg

4.读取到数值2，直接加入逆波兰表达式集合

_images/4.3.41.jpg

5.读取到闭圆括号，依次从运算符栈弹出运算符追到到逆波兰，直到遇到开圆括号。

_images/4.3.51.jpg

6.读取到运算符“*”，此时，栈为空，直接入栈。

_images/4.3.61.jpg

7.读取到运算符开圆括号“（”，直接入符号栈（入栈后，优先级最弱）

_images/4.3.71.jpg

8.读取到数值3，直接加入逆波兰表达式的集合

_images/4.3.81.jpg

9.读取到运算符“+”，栈顶为（，+直接入符号栈

_images/4.3.91.jpg

10.读取到数值4，直接加入逆波兰表达式的集合

_images/4.3.101.jpg

11.读取到闭圆括号，依次从运算符栈弹出运算符追到到逆波兰，直到遇到开圆括号。

_images/4.3.111.jpg

12.表达式解析完成，遍历运算符栈，依次弹出运算符追加到逆波兰表达式。栈空为止。

_images/4.3.121.jpg
扫描表达式 operStack postFixList
( (  
(1 ( 1
(1+ (+ 1
(1+2 (+ 12
(1+2)   12+
(1+2)* * 12+
(1+2)*( *( | 12+ | | (1+2)*(3 | *( 12+3
(1+2)*(3+ *(+ | 12+3 | | (1+2)*(3+4 | *(+ 12+34
(1+2)*(3+4) * 12+34+

最后转换的结果为：12+34+*

3.5.5. 4.6.3.中缀转后缀代码实现

/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: MyCalculator.java
* @Package com.tuling.calculator
* @Description:
* @author 北京图灵学院
* @date 2019年12月3日
* @version V1.0
*/

package com.tuling.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
* @ClassName: MyCalculator
* @Description:
* @author 小白
* @date 2019年12月3日
*
*/

public class MyCalculator {
    //准备一个栈存放运算符
    private MyStack operStack;
    //准备一个集合存放逆波兰表达式
    private List<String> postFixList;
    //准备一个集合存放拆分后的原始表达式
    private List<String> sourceExp;

    /**
     * 创建一个新的实例 MyCalculator.
     *
     */
    public MyCalculator() {
        operStack = new MyStack(20);
        postFixList = new ArrayList<String>();
        sourceExp = new ArrayList<String>();
    }

    /**
    *
    * @Title: inFixConvertPostFix
    * @Description:将原始表达式拆分后，转换为逆波兰表达式
    *   思路：将原始表达式拆分后，逐个解析
    *       1、如果是数字，直接添加到逆波兰表达式
    *       2、如果是运算符
    *           2.1 如果为开圆括号，直接入运算符栈
    *           2.2 如果为闭圆括号，则需依次减弹出栈顶运算符加入到逆波兰表达式，直至遇到开源括号。
    *           2.3 如果为 +-*\/
    *               2.3.1> 运算符栈为空，直接将运算符入栈
    *               2.3.2> 运算符栈不为空
    *                   2.3.2.1> 如果当前栈顶为开圆括号，直接入栈（开圆括号入栈后优先级最低）
    *                   2.3.2.2> 如果当前运算符优先级小于或等于栈顶运算符，则将栈顶弹出，加入到逆波兰是，直至大于。
    * @param expression：原始的中缀表达式
    * @param
    * @return List<String>
    * @throws
    */
    public List<String> inFixConvertPostFix(String expression){
        //将原始中缀表达式拆分
        getExpList(expression);

        //遍历原始表达式，逐个解析
        for(String str:sourceExp) {
            if(isNum(str)) {
                //数字，直接加入到逆波兰表达式
                postFixList.add(str);
            }else if(isOper(str)) {

                if(operStack.isEmpty()) {
                    //当前运算符栈为空，直接入栈
                    operStack.push(str);
                }else {

                    //先处理比较特殊的开圆括号
                    if("(".equals(operStack.peek())) {
                        //如果栈顶是开圆括号，优先级最低，直接入栈
                        operStack.push(str);
                    }else {//处理其他运算符
                        switch (str) {
                            case "(":
                                operStack.push(str);
                                break;
                            case ")":
                                String oper = operStack.pop();
                                while(!"(".equals(oper)) {
                                    //将栈顶的运算符追加到逆波兰表达式
                                    postFixList.add(oper);
                                    //继续弹出栈顶，进行判断。
                                    oper = operStack.pop();
                                }
                                break;
                            case "+":
                            case "-":
                            case "*":
                            case "/":
                                while(!operStack.isEmpty() && priority(str) <= priority(operStack.peek())) {
                                    postFixList.add(operStack.pop());
                                }
                                //记得将当前运算符入栈
                                operStack.push(str);
                                break;
                            default:
                                break;
                        }


                    }


                }

            }
        }

        //表达式解析完成，将运算符栈中逐个添加至逆波兰表达式
        while(!operStack.isEmpty()) {
            postFixList.add(operStack.pop());
        }
        return postFixList;
    }

    /**
    *
    * @Title: priority
    * @Description:返回运算符的优先级
    *   括号返回：3
    *   乘除返回：2
    *   加减返回：1
    * @param oper
    * @param
    * @return int
    * @throws
    */
    public int priority(String oper) {
        switch (oper) {
        case "(":
            return 3;
        case "*":
        case "/":
            return 2;
        case "+":
        case "-":
            return 1;

        default:
            return 0;
        }
    }

    /**
    * @Title: isOper
    * @Description:判断是否为运算符
    * @param @param str
    * @param @return
    * @return boolean
    * @throws
    */
    private boolean isOper(String str) {
        return str.matches("[\\+\\-\\*\\/\\(\\)]");
    }

    /**
    * @Title: isNum
    * @Description:判断是否为数字
    * @param @param str
    * @param @return
    * @return boolean
    * @throws
    */
    private boolean isNum(String str) {
        return str.matches("[0-9]+");
    }

    /**
    * @Title: getExpList
    * @Description:将原始的中缀表达式拆分为集合
    * @param expression
    * @return void
    * @throws
    */
    private void getExpList(String expression) {
        StringTokenizer st = new StringTokenizer(expression, "+-*/()", true);
        while(st.hasMoreTokens()) {
            sourceExp.add(st.nextToken());
        }
    }
}

测试类代码如下：

/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: Test.java
* @Package com.tuling.calculator
* @Description:
* @author 北京图灵学院
* @date 2019年11月28日
* @version V1.0
*/

package com.tuling.calculator;

import java.util.List;

/**
* @ClassName: Test
* @Description:
* @author 小白
* @date 2019年11月28日
*
*/

public class Test {

    /**
    * @Title: main
    * @Description:
    * @param @param args
    * @return void
    * @throws
    */

    public static void main(String[] args) {

//      String expression = "7*2*2-5+1-5+3-44";
        String expression = "(1+2)*(3+4)";
//      String expression = "3+3*5";

        MyCalculator mc = new MyCalculator();
        List<String> postFixList = mc.inFixConvertPostFix(expression);

        System.out.println("中缀表达式：" + expression);
        System.out.print("后缀表达式：");
        for(String str:postFixList) {
            System.out.print(str);
        }
        System.out.println();
    }
}

运行效果如下：

3.5.6. 4.6.4.后缀表达式计算原理分析

  1. 准备工作：一个存储数值的数值栈
  2. 功能实现：逐个解析逆波兰表达式
    1. 如果是数值，直接入数值栈
    2. 如果是运算符，则需从数值栈中弹出两个数，进行运算，并将结果重新入数值栈
    3. 重复前两步，直到遍历解析完逆波兰表达式
    4. 此时数值栈中剩下的一个数即为表达式运算结果

3.5.7. 4.6.5.后缀表达式计算原理图解

还是用表达式：(1+2)*(3+4)来举个例子 逆波兰计法为：12+34+* 如下图所示

1.读取 postFixList 中的第一个元素，为数值 1 ，直接入数值栈

_images/4.4.11.jpg

2.读取 postFixList 中的第二个元素，为数值 2 ，直接入数值栈

_images/4.4.21.jpg

3.读取 postFixList 中的第三个元素，运算符 +

，弹出栈顶的2，弹出栈顶的1，相加的结果重新入数值栈 .. image:: _static/4.栈/4.4后缀表达式计算原理图解/4.4.3.jpg 4.读取 postFixList 中的第四个元素，为数值 3 ，直接入数值栈

_images/4.4.41.jpg

5.读取 postFixList 中的第五个元素，为数值 4 ，直接入数值栈

_images/4.4.51.jpg

6.读取 postFixList 中的第六个元素，运算符 + ，弹出栈顶的4，弹出栈顶的3，相加的结果重新入数值栈

_images/4.4.61.jpg

7.读取 postFixList 中的第七个元素，运算符 * ，弹出栈顶的7，弹出栈顶的3，相乘的结果重新入数值栈

_images/4.4.71.jpg

8.逆波兰表达式解析完成，此时栈顶的数即为表达式的运算结果

_images/4.4.81.jpg

4.6.6.后缀表达式计算代码实现

/**
     *
     * @Title: calculate
     * @Description:计算逆波兰式
     *  思路：准备一个数值栈，逐个遍历逆波兰式，如果是数字，入数值栈，如果是运算符
     *      从数值栈中弹出两个数值，将计算结果重新压入数值栈。直到逆波兰式的最后一个运算符完成。
     * @param: @param postList
     * @param: @return
     * @return: int
     * @throws
     */
    public int calculate(List<String> postList) {
        MyStack numStack = new MyStack(10);
        for(String str:postList) {
            if(isNum(str)) {
                numStack.push(str);
            }else if(isOper(str)) {

                String num1 = numStack.pop();
                String num2 = numStack.pop();

                int result = cla(Integer.parseInt(num1),Integer.parseInt(num2),str);
                //运算结果重新入数值栈
                numStack.push(result+"");
            }
        }

        return Integer.parseInt(numStack.pop());
    }


    /**
     * @Title: cla
     * @Description:
     * @param: @param num1
     * @param: @param num2
     * @param: @param str
     * @param: @return
     * @return: int
     * @throws
     */
    private int cla(int num1, int num2, String oper) {
        int result = 0;
        switch (oper) {
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num2 - num1;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }

MyCalculator.java 类完整代码如下：

/**
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title:  MyCalculator.java
 * @Package com.tuling.calculator
 * @Description:
 * @author: 小白
 * @Date 2019年12月3日 下午9:03:20
 * @version V1.0
 * @Copyright:
 */
package com.tuling.calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @ClassName MyCalculator
 * @Description
 * @Author 北京图灵学院
 * @Date 2019年12月3日 下午9:03:20
 */
public class MyCalculator {

    // 存放原始表达式拆分后的字符串
    private List<String> sourceExp;
    // 用来存放运算符的栈
    private MyStack operStack;
    // 用来存放后缀表达式的栈
    private List<String> postFixList;

    public MyCalculator() {
        sourceExp = new ArrayList<String>();
        operStack = new MyStack(20);
        postFixList = new ArrayList<String>();
    }

    /**
     *
     * @Title: calculate
     * @Description:计算逆波兰式
     *  思路：准备一个数值栈，逐个遍历逆波兰式，如果是数字，入数值栈，如果是运算符
     *      从数值栈中弹出两个数值，将计算结果重新压入数值栈。直到逆波兰式的最后一个运算符完成。
     * @param: @param postList
     * @param: @return
     * @return: int
     * @throws
     */
    public int calculate(List<String> postList) {
        MyStack numStack = new MyStack(10);
        for(String str:postList) {
            if(isNum(str)) {
                numStack.push(str);
            }else if(isOper(str)) {

                String num1 = numStack.pop();
                String num2 = numStack.pop();

                int result = cla(Integer.parseInt(num1),Integer.parseInt(num2),str);
                //运算结果重新入数值栈
                numStack.push(result+"");
            }
        }

        return Integer.parseInt(numStack.pop());
    }


    /**
     * @Title: cla
     * @Description:
     * @param: @param num1
     * @param: @param num2
     * @param: @param str
     * @param: @return
     * @return: int
     * @throws
     */
    private int cla(int num1, int num2, String oper) {
        int result = 0;
        switch (oper) {
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num2 - num1;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }

    /**
     *
     * @Title: inFixConvertPostFix
     * @Description:
     * @param: @param expression
     * @param: @return
     * @return: List<String>
     * @throws
     */
    public List<String> inFixConvertPostFix(String expression) {
        //先将原始中缀表达式拆分。
        getExpList(expression);

        //逐个遍历拆分后的原始表达式
        for (String str : sourceExp) {
            // 如果是数字，直接将数字加入到后缀表达式的集合
            if (isNum(str)) {
                postFixList.add(str);
            } else {// 如果是运算符
                    //
                if (operStack.isEmpty()) {// 如果当前运算符栈为空
                    // 直接将运算符入栈
                    operStack.push(str);
                } else {// 当前运算符栈不为空

                    // 判断特殊的开圆括号
                    if (operStack.peek().equals("(")) {
                        operStack.push(str);
                        continue;
                    }

                    switch (str) {
                    case "(":
                        operStack.push(str);
                        break;
                    case ")":
                        String oper = operStack.pop();
                        while (!"(".equals(oper)) {
                            // 将栈顶的运算符追到到后缀表达式中.
                            postFixList.add(oper);
                            oper = operStack.pop();
                        }
                        break;
                    case "+":
                    case "-":
                    case "*":
                    case "/":
                        while (!operStack.isEmpty() && priority(str) <= priority(operStack.peek())) {
                            postFixList.add(operStack.pop());
                        }
                        // 记得将当前运算符入栈
                        operStack.push(str);
                        break;
                    default:
                        break;
                    }
                }
            }
        }
        while (!operStack.isEmpty()) {
            postFixList.add(operStack.pop());
        }

        return postFixList;
    }

    /**
     *
     * @Title: isNum
     * @Description:判断是否为数字
     * @param
     * @param str
     * @param:
     * @return
     * boolean @throws
     */
    public boolean isNum(String str) {
        return str.matches("[0-9]+");
    }

    /**
     *
     * @Title: isOper
     * @Description:判断是否为为操作符
     * @param str
     * @param:
     * @return boolean
     * @throws
     */
    public boolean isOper(String str) {
        return str.matches("[\\+\\-\\*\\/\\(\\)]");
    }

    /**
     *
     * @Title: getExpList
     * @Description:将原始的表达式拆分为字符串
     * @param
     * @param expression:
     * @return void
     * @throws
     */
    public void getExpList(String expression) {
        StringTokenizer stringTokenizer = new StringTokenizer(expression, "+-*/()", true);
        while (stringTokenizer.hasMoreTokens()) {
            sourceExp.add(stringTokenizer.nextToken());
        }
    }

    /**
     *
     * @Title: priority
     * @Description:返回运算符的优先级 1:开圆括号（ 返回 3 2:乘* 除/ 返回 2 3:加+ 减- 返回 1
     * @param oper
     * @param:
     * @return int
     * @throws
     */
    public int priority(String oper) {
        switch (oper) {
        case "(":
            return 1;
        case "*":
        case "/":
            return 3;
        case "+":
        case "-":
            return 2;
        default:
            return 0;
        }
    }

    /**
     * @return sourceExp
     */
    public List<String> getSourceExp() {
        return sourceExp;
    }

    /**
     * @param sourceExp
     *            the sourceExp to set
     */
    public void setSourceExp(List<String> sourceExp) {
        this.sourceExp = sourceExp;
    }

    /**
     * @return operStack
     */
    public MyStack getOperStack() {
        return operStack;
    }

    /**
     * @param operStack
     *            the operStack to set
     */
    public void setOperStack(MyStack operStack) {
        this.operStack = operStack;
    }

    /**
     * @return postFixList
     */
    public List<String> getPostFixList() {
        return postFixList;
    }

    /**
     * @param postFixList
     *            the postFixList to set
     */
    public void setPostFixList(List<String> postFixList) {
        this.postFixList = postFixList;
    }
}

4.6.7.计算器UI界面代码

/**
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title:  CalculatorFrame.java
 * @Package com.tuling.calculator
 * @Description:
 * @author: 小白
 * @Date 2019年12月4日 下午4:14:20
 * @version V1.0
 * @Copyright:
 */
package com.tuling.calculator;

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.List;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JTextField;
import javax.swing.SwingUtilities;

public class CalculatorFrame extends JFrame implements ActionListener{

    private static final long serialVersionUID = 1L;
    private JPanel jContentPane = null;
    private JPanel jPanel = null;
    private JPanel jPanel1 = null;
    private JPanel jPanel2 = null;
    private JTextField jTextField_exp = null;
    private JButton jButton_AC = null;
    private JButton jButton_start = null;
    private JButton jButton_end = null;
    private JButton jButton_add = null;
    private JButton jButton_seven = null;
    private JButton jButton_eight = null;
    private JButton jButton_nine = null;
    private JButton jButton_minus = null;
    private JButton jButton_four = null;
    private JButton jButton_five = null;
    private JButton jButton_six = null;
    private JButton jButton_cheng = null;
    private JButton jButton_one = null;
    private JButton jButton_two = null;
    private JButton jButton_three = null;
    private JButton jButton_chu = null;
    private JButton jButton_zero = null;
    private JButton jButton_result = null;

    /**
     * This method initializes jPanel
     *
     * @return javax.swing.JPanel
     */
    private JPanel getJPanel() {
        if (jPanel == null) {
            FlowLayout flowLayout = new FlowLayout();
            flowLayout.setAlignment(FlowLayout.LEFT);
            jPanel = new JPanel();
            jPanel.setLayout(flowLayout);
            jPanel.setName("jPanel");
            jPanel.add(getJTextField_exp(), null);
        }
        return jPanel;
    }

    /**
     * This method initializes jPanel1
     *
     * @return javax.swing.JPanel
     */
    private JPanel getJPanel1() {
        if (jPanel1 == null) {
            GridLayout gridLayout1 = new GridLayout();
            gridLayout1.setRows(4);
            gridLayout1.setHgap(10);
            gridLayout1.setVgap(5);
            gridLayout1.setColumns(4);
            jPanel1 = new JPanel();
            jPanel1.setName("jPanel1");
            jPanel1.setLayout(gridLayout1);
            jPanel1.add(getJButton_AC(), null);
            jPanel1.add(getJButton_start(), null);
            jPanel1.add(getJButton_end(), null);
            jPanel1.add(getJButton_add(), null);
            jPanel1.add(getJButton_seven(), null);
            jPanel1.add(getJButton_eight(), null);
            jPanel1.add(getJButton_nine(), null);
            jPanel1.add(getJButton_minus(), null);
            jPanel1.add(getJButton_four(), null);
            jPanel1.add(getJButton_five(), null);
            jPanel1.add(getJButton_six(), null);
            jPanel1.add(getJButton_cheng(), null);
            jPanel1.add(getJButton_one(), null);
            jPanel1.add(getJButton_two(), null);
            jPanel1.add(getJButton_three(), null);
            jPanel1.add(getJButton_chu(), null);
        }
        return jPanel1;
    }

    /**
     * This method initializes jPanel2
     *
     * @return javax.swing.JPanel
     */
    private JPanel getJPanel2() {
        if (jPanel2 == null) {
            FlowLayout flowLayout1 = new FlowLayout();
            flowLayout1.setHgap(10);
            flowLayout1.setVgap(5);
            jPanel2 = new JPanel();
            jPanel2.setLayout(flowLayout1);
            jPanel2.setName("jPanel2");
            jPanel2.add(getJButton_zero(), null);
            jPanel2.add(getJButton_result(), null);
        }
        return jPanel2;
    }

    /**
     * This method initializes jTextField_exp
     *
     * @return javax.swing.JTextField
     */
    private JTextField getJTextField_exp() {
        if (jTextField_exp == null) {
            jTextField_exp = new JTextField();
            jTextField_exp.setColumns(26);
            jTextField_exp.setText("0");
            jTextField_exp.setFont(new Font("Dialog", Font.PLAIN, 18));
        }
        return jTextField_exp;
    }

    /**
     * This method initializes jButton_AC
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_AC() {
        if (jButton_AC == null) {
            jButton_AC = new JButton();
            jButton_AC.setText("AC");
            jButton_AC.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_AC;
    }

    /**
     * This method initializes jButton_start
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_start() {
        if (jButton_start == null) {
            jButton_start = new JButton();
            jButton_start.setText("(");
            jButton_start.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_start;
    }

    /**
     * This method initializes jButton_end
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_end() {
        if (jButton_end == null) {
            jButton_end = new JButton();
            jButton_end.setText(")");
            jButton_end.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_end;
    }

    /**
     * This method initializes jButton_add
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_add() {
        if (jButton_add == null) {
            jButton_add = new JButton();
            jButton_add.setText("+");
            jButton_add.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_add;
    }

    /**
     * This method initializes jButton_seven
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_seven() {
        if (jButton_seven == null) {
            jButton_seven = new JButton();
            jButton_seven.setText("7");
            jButton_seven.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_seven;
    }

    /**
     * This method initializes jButton_eight
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_eight() {
        if (jButton_eight == null) {
            jButton_eight = new JButton();
            jButton_eight.setText("8");
            jButton_eight.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_eight;
    }

    /**
     * This method initializes jButton_nine
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_nine() {
        if (jButton_nine == null) {
            jButton_nine = new JButton();
            jButton_nine.setText("9");
            jButton_nine.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_nine;
    }

    /**
     * This method initializes jButton_minus
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_minus() {
        if (jButton_minus == null) {
            jButton_minus = new JButton();
            jButton_minus.setText("-");
            jButton_minus.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_minus;
    }

    /**
     * This method initializes jButton_four
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_four() {
        if (jButton_four == null) {
            jButton_four = new JButton();
            jButton_four.setText("4");
            jButton_four.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_four;
    }

    /**
     * This method initializes jButton_five
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_five() {
        if (jButton_five == null) {
            jButton_five = new JButton();
            jButton_five.setText("5");
            jButton_five.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_five;
    }

    /**
     * This method initializes jButton_six
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_six() {
        if (jButton_six == null) {
            jButton_six = new JButton();
            jButton_six.setText("6");
            jButton_six.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_six;
    }

    /**
     * This method initializes jButton_cheng
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_cheng() {
        if (jButton_cheng == null) {
            jButton_cheng = new JButton();
            jButton_cheng.setText("*");
            jButton_cheng.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_cheng;
    }

    /**
     * This method initializes jButton_one
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_one() {
        if (jButton_one == null) {
            jButton_one = new JButton();
            jButton_one.setText("1");
            jButton_one.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_one;
    }

    /**
     * This method initializes jButton_two
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_two() {
        if (jButton_two == null) {
            jButton_two = new JButton();
            jButton_two.setText("2");
            jButton_two.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_two;
    }

    /**
     * This method initializes jButton_three
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_three() {
        if (jButton_three == null) {
            jButton_three = new JButton();
            jButton_three.setText("3");
            jButton_three.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_three;
    }

    /**
     * This method initializes jButton_chu
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_chu() {
        if (jButton_chu == null) {
            jButton_chu = new JButton();
            jButton_chu.setText("/");
            jButton_chu.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_chu;
    }

    /**
     * This method initializes jButton_zero
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_zero() {
        if (jButton_zero == null) {
            jButton_zero = new JButton();
            jButton_zero.setText("   0   ");
            jButton_zero.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_zero;
    }

    /**
     * This method initializes jButton_result
     *
     * @return javax.swing.JButton
     */
    private JButton getJButton_result() {
        if (jButton_result == null) {
            jButton_result = new JButton();
            jButton_result.setText("   =   ");
            jButton_result.setFont(new Font("Dialog", Font.BOLD, 24));
        }
        return jButton_result;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                CalculatorFrame thisClass = new CalculatorFrame();
                thisClass.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                thisClass.setVisible(true);
            }
        });
    }

    /**
     * This is the default constructor
     */
    public CalculatorFrame() {
        super();
        initialize();
    }

    /**
     * This method initializes this
     *
     * @return void
     */
    private void initialize() {
        this.setSize(400, 370);
        this.setContentPane(getJContentPane());
        this.setTitle("图灵计算器V1.0");

        Toolkit tool = Toolkit.getDefaultToolkit();
        Dimension d = tool.getScreenSize();
        int x = (int) ((d.getWidth() - 400) / 2);
        int y = (int) ((d.getHeight() - 370) / 2);

        this.setLocation(x, y);

        addListener();
    }

    private void addListener() {
        this.jButton_AC.addActionListener(this);
        jButton_start.addActionListener(this);
        jButton_end.addActionListener(this);
        jButton_add.addActionListener(this);
        jButton_seven.addActionListener(this);
        jButton_eight.addActionListener(this);
        jButton_nine.addActionListener(this);
        jButton_minus.addActionListener(this);
        jButton_four.addActionListener(this);
        jButton_five.addActionListener(this);
        jButton_six.addActionListener(this);
        jButton_cheng.addActionListener(this);
        jButton_one.addActionListener(this);
        jButton_two.addActionListener(this);
        jButton_three.addActionListener(this);
        jButton_chu.addActionListener(this);
        jButton_zero.addActionListener(this);
        jButton_result.addActionListener(this);
    }

    /**
     * This method initializes jContentPane
     *
     * @return javax.swing.JPanel
     */
    private JPanel getJContentPane() {
        if (jContentPane == null) {
            BorderLayout borderLayout = new BorderLayout();
            borderLayout.setHgap(10);
            borderLayout.setVgap(0);
            GridLayout gridLayout2 = new GridLayout();
            gridLayout2.setRows(3);
            gridLayout2.setColumns(1);
            GridLayout gridLayout11 = new GridLayout();
            gridLayout11.setRows(3);
            gridLayout11.setColumns(1);
            GridLayout gridLayout = new GridLayout();
            gridLayout.setRows(3);
            gridLayout.setColumns(1);
            jContentPane = new JPanel();
            jContentPane.setLayout(borderLayout);
            jContentPane.add(getJPanel(), BorderLayout.NORTH);
            jContentPane.add(getJPanel1(), BorderLayout.CENTER);
            jContentPane.add(getJPanel2(), BorderLayout.SOUTH);
        }
        return jContentPane;
    }

    private String expression = "";  //  @jve:decl-index=0:

    @Override
    public void actionPerformed(ActionEvent e) {
        String command = e.getActionCommand().trim();

        if (command.equals("AC")) {
            expression = "";
            jTextField_exp.setText("0");
        } else if (command.equals("=")) {
            expression = jTextField_exp.getText().trim();
            //TODO:表达式合法判断
            MyCalculator mc = new MyCalculator();

            System.out.println("中缀表达式：" + expression);

            //转后缀表达式
            List<String> postFixList = mc.inFixConvertPostFix(expression);

            System.out.print("后缀表达式：");
            for(String str:postFixList) {
                System.out.print(str);
            }
            System.out.println();

            //开始计算
            int result = mc.calculate(postFixList);



            System.out.println("计算结果为：" + result);

            expression = result+"";
            jTextField_exp.setText(result+"");

        } else {
            expression += command;
            jTextField_exp.setText(expression);
        }

    }

}  //  @jve:decl-index=0:visual-constraint="10,10"
_images/201912041646411.jpg