逆波兰表达式

本文主要是介绍逆波兰表达式，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈的应用

1.使用栈计算一个表达式的结果，如：7x2x5-3-6+5+9 （中缀表达式）

思路：创建两个栈，一个存储数据，一个存储用算符；

① 定义一个index索引，遍历表达式

② 如果为数字进入数据栈；

③ 若为符号，判断如果当前符号栈为null则直接压入，若不为null,则比较优先级大小，如果当前符号小于等于栈中符号优先级，就需要从数据栈栈中弹出两个数，从符号栈中弹出一个符号，进行与运算，将得到的结果入数据栈，然后将当前运算符入符号栈；如果当前符号大于栈中符号优先级，直接入符号栈；

④ 当表达式扫描完，就顺序从数栈和符号栈中pop出相应的数和符号，并运算；

⑤ 最后数栈中只有一个数，为结果；

package com.sratct.stack;

public class StackList {
    public static void main(String[] args) {
        StackArray numStack = new StackArray(10); // 数栈
        StackArray operStack = new StackArray(10); // 符号栈
        String expression = "30+2*6-2";
        char[] chars = expression.toCharArray();
        int num1 = 0;  // 弹出第一个数
        int num2 = 0; // 弹出第二个数
        int val = 0; // 运算的结果
        int oper = 0; //接收运算符
        String keepNumber = ""; //用于拼接多位数
        int i=0;
        for (char ch : chars) {
            // 判断当前的元素是不是运算符
            if (operStack.isOper(ch)) {
                // 是运算符，判断符号栈中是否有元素
                if (!operStack.isEmpty()) {
                    // 不为空，判断当前运算符和符号栈中的运算符优先级，
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        //小于等于， 从符号栈中pop出一个元素，从数栈中pop出两个元素,运算后结果入数栈
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        val = operStack.cal(num1, num2, oper);
                        numStack.push(val);
                        operStack.push(ch);
                    } else {
                        //大于，直接插入
                        operStack.push(ch);
                    }

                } else{
                    // 为空，直接插入
                    operStack.push(ch);
                }
            } else {
                // 是数字时，不能立即入数栈，由于数字为字符会将多位数分成几个字符；如：13 ==> '1' 和 '3'
                // 在处理多为数时，需要当前元素后再看一位，如果为符号则入数栈，不是则继续往后走；
                // 每次将字符拼接到keepNumber中进行保存
                keepNumber += ch;
               //  如果ch是最后一位，则直接入入栈
                if (i == expression.length()-1) {
                    numStack.push(Integer.parseInt(keepNumber));
                } else {
                    // 判断下一位ch是不是数字，若为数字，继续看下一位，若为运算符，则入数栈
                    if (operStack.isOper(chars[i+1])) {
                        numStack.push(Integer.parseInt(keepNumber));
                        // 清空keepNumber
                        keepNumber = "";
                    }
                }
            }
            i++;
        }

        // 当运算表达式循环完毕，就继续从符号栈中弹出一个，从数栈中弹出两个进行运算，直到符号栈中为空，最终数栈中剩下的为最终结果
       while (true) {
           if (operStack.isEmpty()) {
               break;
           }
           num1 = numStack.pop();
           num2 = numStack.pop();
           oper = operStack.pop();
           val = operStack.cal(num1,num2,oper);
           numStack.push(val);
       }
        System.out.println(numStack.pop());
    }
}

class StackArray {
    private int maxSize;
    private int top;
    private int[] arrayStack;

    public StackArray(int maxSize) {
        this.maxSize = maxSize;
        arrayStack = new int[maxSize];
        top = -1;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 判断栈是否满
    public boolean isFull() {
        return top == maxSize-1;
    }

    // 查看栈首元素
    public int peek() {
      return arrayStack[top];
    }

    // 入栈
    public void push(int data) {
        if (isFull()) {
            System.out.println("栈已满");
            return;
        }
        top++;
        arrayStack[top] = data;

    }
    // 出栈
    public int pop() {
        if (isEmpty()) {
           throw new RuntimeException("栈为null");
        }
        int temp = arrayStack[top];
        top--;
        return temp;
    }
    //遍历栈
    public void getList() {
        if (isEmpty()) {
            System.out.println("栈为null");
            return;
        }
        for (int i=top; i>=0; i--) {
            System.out.println(arrayStack[i]);
        }
    }

    // 返回运算符的优先级，自己定义，目前只有+、-、*、/
    public int priority(int oper){
       if (oper == '*' || oper == '/') {
           return 1;
       } else if (oper == '+' || oper == '-') {
           return 0;
       } else {
           return -1;
       }
    }

    // 判断该元素是不是运算符
    public boolean isOper(char val) {
        return val=='*' || val == '/' || val == '+' || val == '-';
    }

    // 两个数进行运算
    public int cal(int num1,int num2,int oper) {
        int val = 0;
        switch (oper) {
            case '-':
                val = num2-num1;  // 注意，后弹出的数减去前一个数
                break;
            case '+':
                val = num1 + num2;
                break;
            case '*':
                val =num1 * num2;
                break;
            case '/':
                val = num2 / num1;
                break;
            default:
                break;
        }
        return val;
    }
}

2.前缀(波兰表达式)、中缀、后缀表达式(逆波兰表达式)

1） 前缀表达式的计算机求值

从右至左扫描的表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈，重复上述操作直到表达式的最左端，最后运算得到的值即为表达式的结果；

例如： （3+4）x 5 - 6对应的前缀表达式为： - x + 3 4 5 6 ,求值如下步骤：

① 从右至左扫描，将6、5、4、3压入堆栈；

② 遇到+号时，弹出3和4，计算3+4的值为7，再将7压入栈；

③ 接下来是 x 运算符，因此弹出7和5，计算7 x 5 =35,将35入栈；

④ 最后是 - 运算符，计算出35 - 6的值，即29，由此得到最终结果；

2） 中缀表达式

中缀表达式就是我们常见的表达式： （3+4）x 5 - 6

此表达式对我们人来说是非常容易计算，但是计算机就不好操作，计算机在计算结果时一般采用后缀表达式；

3）后缀表达式

① 后缀表达式又称逆波兰表达式

② 举例：（3+4）x 5 - 6对应的后缀表达式为3 4 + 5 x 6 -

③后缀表达式的计算机求值

从左至右扫描表达式，遇到数字，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈，重复上述操作直到表达式的最左端，最后运算得到的值即为表达式的结果；

例如： （3+4）x 5 - 6对应的前缀表达式为：3 4 + 5 x 6 - ,求值如下步骤：

① 从左至右扫描，将3、4压入堆栈；

② 遇到+号时，弹出3和4，计算3+4的值为7，再将7压入栈；

③ 将5入栈

④ 接下来是 x 运算符，因此弹出5和7，计算7 x 5 =35,将35入栈；

⑤ 将6入栈

④ 最后是 - 运算符，计算出35 - 6的值，即29，由此得到最终结果；

3.中缀表达式转后缀表达式

具体步骤：

1） 初始化两个栈，存储运算符栈s1和处理中间结果的栈s2;

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

3）遇到数字时压入s2;

4） 遇到运算符时，比较当前运算符与栈顶元素运算符的优先级；

​ ① 如果栈s1中为空，或者栈顶为 "(",则直接入栈；

​ ② 若当前运算符比栈顶运算符的优先级高，则直接压入s1;

​ ③ 否则，将s1栈顶元素弹出压入到s2,再进行 4）①操作；

5）遇到括号时：

​ ① 遇到 “(” ,则直接入s1栈；

​ ② 遇到 “)”, 则依次弹出弹出s1栈顶的运算符，并压入到s2中，直到遇到 “)” ，此时丢弃了一对括号；

6）重复2）至 5），直到表达式的最右边；

7）表达式遍历完之后，将s1剩余的运算符依次弹出，并压入到s2;

8. 依次输出s2,为逆波兰表达式的逆序；

package com.sratct.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class testBoLan {
    public static void main(String[] args) {
        String bolanString = "10+((2+3)*4)-5";
        // 将中缀表达式转为集合
        List<String> boLanList =  stringToList(bolanString);
        /**
         * 将中缀表达式集合转为后缀表达式集合
         * 1+((2+3)*4)-5 ==> 1 2 3 + 4 * + 5 -
         */
        List<String> stringList = zToOutList(boLanList);

        /**
         * 计算出后缀表达式的值
         * 1 2 3 + 4 * + 5 - => 16
         */
        System.out.println(getResult(stringList));
    }

    /**
     * 字符串转为集合步骤
     *  1.先将字符串转为字符数组，遍历
     *  2.根据ASCII码值，数字的[0-9]对应的值是[48-57]，所以判断字符是否为数字，不是数字直接放入集合中
     *  3.若为数字，需要考虑多位数
     *     判断是字符数组的最后一位数字则直接放入集合
     *     若不是最后一位，则需继续向下一位判断并将数字拼接，直到下一位是字符，然后将拼接好的字符数放入集合
     * @param bolanString
     * @return
     */
    private static List<String> stringToList(String bolanString) {
        char[] chars = bolanString.toCharArray();
        List<String> stringList = new ArrayList<>();
        int i= 0;
        String res = ""; // 拼接字符数字
        for (char ch : chars) {
            // 判断字符是否为数字
            if (ch <48 || ch >57) {
                // 字符
                stringList.add(ch + "");
            } else {
                res += ch;
                if (i == bolanString.length()-1) { // 如果已经为最后一位则直接放入集合中
                    stringList.add(res);
                } else {
                    if (chars[i+1] < 48 || chars[i+1] >57) { //如果下一位不是数字，则放入到集合中，并将res清空
                        stringList.add(res);
                        res = "";
                    }
                }
            }
            i++;
        }
        return stringList;
    }

    /**
     * 中缀表达式转后缀表达式
     * @param boLanList
     * @return
     */
    private static List<String> zToOutList(List<String> boLanList) {
        Stack<String> s1 = new Stack<>(); // 存放符号
        List<String> s2 = new ArrayList<>(); // 存放结果

        boLanList.forEach(s -> {
            // 判断当前元素是否为数字
            if (s.matches("\\d+")) {
                s2.add(s);   // 为数字直接放入s2
            } else if (s1.size() == 0 || s.equals("(")){ // 若当前元素为"("，或栈中为null直接入栈s1
                s1.push(s);
            } else if (s.equals(")")) { // 若当前元素为")"，则依次弹出s1栈中元素放入到s2中，直到s1的栈顶元素为"("
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop(); //最后将"(" 弹出，消除掉一对括号
            } else { // 判断当前元素和s1栈顶元素优先级，若当前元素的优先级小于等于栈顶元素，将s1栈顶元素弹出s放入到S2
                while (s1.size() != 0 && (Operation1.getOperation(s) <= Operation1.getOperation(s1.peek()))) {
                    s2.add(s1.pop());
                }
                s1.push(s);
            }
        });

        // 当集合遍历完成，然后将s1栈中的剩余运算符依次放入集合中
        while (s1.size() !=0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     *  计算逆波兰表达式的值,步骤：
     *  如果为数字直接入栈，若为运算符则从栈中弹出两个数进行运算，然后再入栈，最后栈中栈中的元素只剩下一个
     */
    private static int getResult(List<String> stringList) {
        Stack<String> stack = new Stack<>();
        stringList.forEach(s -> {
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int val = cal(num1,num2,s);
                stack.push(val + "");
            }
        });
        return Integer.parseInt(stack.pop());
    }

    /**
     * 计算结果
     * @param num1
     * @param num2
     * @param oper
     * @return
     */
    private static int cal(int num1, int num2, String oper) {
        int val = 0;
        switch (oper){
            case "+":
                val = num1 + num2;
                break;
            case "-":
                val = num2 - num1;
                break;
            case "*":
                val = num1 * num2;
                break;
            case  "/":
                val = num1 / num2;
            default:
                break;
        }
        return val;
    }
}

class Operation1 {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getOperation(String oper) {
        int val = 0;
        switch (oper) {
            case "+" :
              val = ADD;
              break;
            case "-" :
                val = SUB;
                break;
            case "*" :
                val = MUL;
                break;
            case "/" :
                val = DIV;
                break;
            default:
                break;
        }
        return val;
    }
}

这篇关于逆波兰表达式的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！