Java数据结构-栈-简单应用

1，三种表达式

1）三种表达式
四则运算的三种表达方式，用于四则运算表达式求值
中缀表达式：(3+4)*5-6
后缀表达式(逆波兰表达式)：3 4 + 5 * 6 -
前缀表达式(波兰式)：- * + 3 4 5 6
2）中缀表达式转后缀表达式(运算符位于操作数)
步骤一：从左至右扫描表达式，遇到操作数直接到输出栈outputLinkedList
步骤二：遇到运算符时
如果operatorLinkedList为空，则直接入栈
如果(，直接入栈
遇到)，则将(...)直接操作符依次pop并输出到outputLinkedList，并丢弃(
步骤三：与栈顶运算符比较优先级，高于栈顶元素则直接入栈。
低于或者同级，则从栈顶开始，依次pop高于或者同级的运算符，输出到outputLinkedList
3）前缀表达式
从右向左扫描表达式。

image.png

4）使用后缀表达式计算
步骤一：新建一个栈
步骤二：从左到右扫描后缀表达式，遇到数字则直接入栈
步骤三：遇到操作符，则依次弹出Y，X两个元素，计算X ops Y，并将结果入栈。
步骤四：最后输出栈顶的值。
5）(3+4)*5-6 转成后缀表达式的例子
后缀表达式outputLinkedList 操作符栈operatorLinkedList
无 | (
3 | (+
34 | (+) ---> 34+
34+ | *
34+5* | - -的优先级低于*
3 4 + 5 * 6 -

2，Java Demo

package com.hzq.study;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * Created on 2018/4/8.
 */
public class Calculator {

    public static void main(String[] args) {
        //用栈暂存操作符
        LinkedList<String> operators = new LinkedList<>();
        //后缀表达式
        StringBuilder sb = new StringBuilder();
        String str = "6 * ( 5 + ( 2 + 3 ) * 8 + 3 )";
        String [] array = str.split(" ");

        for(String item : array){
            if(isOperators(item)){ //处理操作符
                if(operators.isEmpty()){//栈为空则直接入栈
                    operators.push(item);
                } else {
                    //获取栈顶元素的优先级
                    int stackHeadItemPriority = priority(operators.peek());
                    //获取读入元素的优先级
                    int itemPriority = priority(item);
                    
                    //如果读入元素为")"，则弹出"()"之间的元素到后缀表达式
                    if(")".equals(item)){
                        while (!"(".equals(operators.peek())){
                            String operator = operators.pop();
                            sb.append(operator).append(" ");
                        }

                        if("(".equals(operators.peek())){
                            operators.pop();
                        }
                    //如果读入元素优先级大于栈顶元素，则直接入栈 "("优先级定义为最高，则也会直接入栈
                    } else if(itemPriority > stackHeadItemPriority){
                        operators.push(item);
                    //如果读入元素不为")"，且优先级低于或者同级操作符，则依次弹出到后缀表达式，直到遇到比自己低的操作符。   
                    } else if(itemPriority <= stackHeadItemPriority){
                        while (operators.size() != 0 && !operators.peek().equals("(")){
                            String operator = operators.pop();
                            sb.append(operator).append(" ");
                        }

                        operators.push(item);
                    }
                }
            } else {
                //处理操作数
                sb.append(item).append(" ");
            }
        }
        
        //最后操作符栈不为空，则一次pop到后缀表达式
        if(!operators.isEmpty()){
            Iterator<String> iterator = operators.iterator();
            while (iterator.hasNext()){
                String operator = iterator.next();
                sb.append(operator).append(" ");
                iterator.remove();
            }
        }

        System.out.println("后缀： " + sb);
        System.out.println(calculatorByOperator(sb.toString()));
    }

    /**
     * 判断一个字符串是不是操作符
     * @param str
     * @return
     */
    public static boolean isOperators(String str){
        if("+".equalsIgnoreCase(str) || "-".equalsIgnoreCase(str)
                || "*".equalsIgnoreCase(str) || "/".equalsIgnoreCase(str)
                || "(".equalsIgnoreCase(str) || ")".equalsIgnoreCase(str)){
            return true;
        }

        return false;
    }

    /**
     * 返回操作符的优先级
     * @param str
     * @return
     */
    public static int priority(String str){
        switch (str){
            case "+":
                return 1;
            case "-":
                return 1;
            case "*":
                return 2;
            case "/":
                return 2;
            case "(":
                return 3;
            case ")":
                return 3;
            default:
                return 0;
        }
    }

    /**
     * 使用操作符计算两个操作数
     * @param opsNum1
     * @param opsNum2
     * @param operator
     * @return
     */
    public static int calculator(int opsNum1, int opsNum2, String operator){
        switch (operator){
            case "+":
                return opsNum1 + opsNum2;
            case "-":
                return opsNum1 - opsNum2;
            case "*":
                return opsNum1 * opsNum2;
            case "/":
                return opsNum1 / opsNum2;
            default:
                return 0;
        }
    }

    /**
     * 根据后缀表达式计算值
     * @param postExpression
     * @return
     */
    public static int calculatorByOperator(String postExpression){
        LinkedList<String> tempResultList=new LinkedList<>();//新建一个栈，来存储临时结果
        String[] postArray = postExpression.split(" ");
        for(String str : postArray){//扫描后缀表达式
            if(isOperators(str)){//操作符则弹出栈顶另个元素，Y, X，使用 X [ops] Y计算
                if(!tempResultList.isEmpty()){
                    int numY = Integer.valueOf(tempResultList.pop());
                    int numX = Integer.valueOf(tempResultList.pop());
                    if(str.equals("/") && numY == 0){
                        System.out.println("除数不能为0");
                        throw new RuntimeException("除数不能为0");
                    }
                    int tempResult = calculator(numX, numY, str);
                    tempResultList.push(String.valueOf(tempResult));
                }
            } else {
                tempResultList.push(str);//操作数直接入栈
            }
        }

        return Integer.valueOf(tempResultList.pop());
    }

}