逆波兰表达式

2021/4/17 10:25:27

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

栈的应用

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;

  1. 依次输出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;
    }
}


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


扫一扫关注最新编程教程