经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 计算机原理 » 查看文章
计算器思想-中缀表达式转化为后缀表达式
来源:cnblogs  作者:pretty_spider  时间:2023/9/15 13:31:21  对本文有异议

计算机思维和人的思维的不同

对于一个算式3+2*(4-3)/5
人的思维是根据括号和符号优先级,优先计算括号中的数据,在进行乘法和除法,在处理加法运算
但是计算机的思维是线性的,计算机会按照算式的前后顺序,从前往后进行运算,这样会导致运算结果错误

计算机如何套用人的运算思维

想要让计算机具有人的”思维“,就需要使用栈,将数据和运算符号之间的顺序按照计算机可以理解的方式排列
想要改变规则,就需要将人理解的中缀表达式转换为后缀表达式
转化的规则是:

  • 中缀表达式转化成后缀表达式
    1.遇到操作数直接放入到集合中
    2.遇到操作符
    2.1当栈为空,或栈顶元素为(,直接放入到栈中
    2.2当优先级比栈顶元素高时,直接进栈
    2.3当优先级小于等于栈顶元素,将栈顶元素出栈放入到集合中,再和栈顶元素比较
    3.遇到左右括号
    3.1如果为左括号,直接加入栈
    3.2如果为右括号,依次将栈顶元素弹出,直到左括号,并将左括号弹出
    4.最后将栈顶元素依次弹出

中缀表达式转换为后缀表达式的过程

以运算算式 3-(4-3)/5*10
以中缀表达式表示为 3 - 4 - 3 / 5 * 10
后缀表达式表示为 3 4 3 - 5 / 10 * -
其中涉及到了栈的入栈和出栈,

转化过程:
1.先创建一个集合,用于记录后缀表达式,创建一个栈,用于记录运算符
2.3进入集合,-进入栈 集合 3 栈 -
3.左括号进栈 集合3 栈- (
4.4进入集合,-进入栈,与此时的栈顶元素比较,此时栈顶元素是左括号,-直接放入栈中 集合3 4 栈 - ( -
5.3进入集合,-和栈顶元素比较,优先级相等或者小于,将栈顶元素-弹出 集合中为 3 4 3 - 栈-(
6.右括号进栈 将栈顶元素弹出,直到左括号并弹出左括号 集合3 4 3 - 栈-
7./进栈,优先级大于-,直接进栈,5 进入集合 集合3 4 3 - 5 栈- /
8.*进栈,优先等于栈顶元素,弹出栈顶元素,10进入集合 集合 3 4 3 - 5 / 10 栈 - *
9.算式获取完成,将栈中元素全部弹出 集合 3 4 3 - 5 / 10 * -

实现

整数算式运算

package com.prettyspider.calculate;

import java.util.*;


/**
 * @author prettyspider
 * @ClassName CalcInt
 * @description: 传入整数运算字符串,计算其数值
 * @date 2023/9/11 6:21
 * @Version V1.0
 */

public class CalcInt {
    /**
     * 中缀表达式转化成后缀表达式
     * <p>
     * 1.遇到操作数直接放入到集合中
     * 2.遇到操作符
     * 2.1当栈为空,或栈顶元素为(,直接放入到栈中
     * 2.2当优先级比栈顶元素高时,直接进栈
     * 2.3当优先级小于等于栈顶元素,将栈顶元素出栈放入到集合中,再和栈顶元素比较
     * 3.遇到左右括号
     * 3.1如果为左括号,直接加入栈
     * 3.2如果为右括号,依次将栈顶元素弹出,直到左括号,并将左括号弹出
     * 4.最后将栈顶元素依次弹出
     */
    public static void main(String[] args) {
        // 要传入的运算字符串
        String s = "10+2*(3-4)+20*(3*4+3)/3+20";
        // 中缀表达式转化成后缀表达式
        List<String> list = inToPastExpression(s);
        // 计算
        int number = calc(list);
        System.out.println("计算的数值为"+number);
    }


    /**
     * 计算后缀表达式
     * @param list 后缀表达式集合
     * @return 传入的整数运算字符串的计算数值
     */
    private static int calc(List<String> list) {
        // 创建栈,用于记录数据
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            // 1.放入 当是数值时,直接放入栈中
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                // 2.去除 当是运算符时,再栈中取出两个数,进行运算,并将运算之后的结果放入到栈中
                int num1, num2;
                switch (s) {
                    case "+":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 + num1));
                        break;
                    case "-":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 - num1));
                        break;
                    case "*":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 * num1));
                        break;
                    case "/":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 / num1));
                        break;
                }
            }
        }
        return Integer.parseInt(stack.pop());
    }


    /**
     * 将传入的字符串进行切分,存放到集合中
     * @param str 传入的算数字符串
     * @return 后缀表达式集合
     */
    private static List<String> inToPastExpression(String str) {
        // 创建集合和栈
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        // 切分数据
        ArrayList<String> arr = cutString(str);
        for (int i = 0; i < arr.size(); i++) {
            //       * 1.遇到操作数直接放入到集合中
            String value = arr.get(i);
            if (value.matches("\\d+")) {
                list.add(value);
            }
            //      * 3.遇到左右括号
            //      *      3.1如果为左括号,直接加入群
            else if ("(".equals(value)) {
                stack.push(value);
            }
            //      *      3.2如果为右括号,依次将栈顶元素弹出,直到左括号,并将左括号弹出
            else if (")".equals(value)) {
                while (!"(".equals(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.pop();
            }
            //      * 2.遇到操作符
            else {
                //      *      2.1当栈为空,或栈顶元素为(,直接放入到栈中
                //      *      2.3当优先级小于等于栈顶元素,将栈顶元素出栈放入到集合中,再和栈顶元素比较
                while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
                    list.add(stack.pop());
                }
                //      *      2.2当优先级比栈顶元素高时,直接进栈
                stack.push(value);
            }
        }
        //      * 4.最后将栈顶元素依次弹出
        while (!stack.empty()) {
            list.add(stack.pop());
        }
        System.out.println(list);
        return list;
    }

    /**
     * 将运算字符切分切分成集合
     * @param str 待切分字符串
     * @return ArrayList<String> 被切分之后的字符串集合
     */
    private static ArrayList<String> cutString(String str) {
        String[] arr = new String[str.length()-1];
        // 为字符串数组赋初值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "";
        }
        int index = 0;
        arr[index] = String.valueOf(str.charAt(0));
        for (int i = 1; i < str.length(); i++) {
            // 1.是数值放入
            if (Character.isDigit(str.charAt(i))) {
                // 1.1并看其起一个数据是不是也数值,是数值,将其前一个数据*10+本身
                if (arr[index].matches("\\d+")) {
                    arr[index] = String.valueOf(Integer.parseInt(arr[index]) * 10 + Integer.parseInt(String.valueOf(str.charAt(i))));
                } else {
                    arr[++index] = String.valueOf(str.charAt(i));
                }
            } else {
                // 2.不是数值,直接加入到集合中
                arr[++index] = String.valueOf(str.charAt(i));
            }
        }
        // 去除null
        ArrayList<String> list = removeNull(arr);
        return list;

    }

    /**
     * 将字符串数组中为空的元素去除
     * @param arr 字符串数组
     * @return 去除控制的字符串集合
     */
    private static ArrayList<String> removeNull(String[] arr) {
        ArrayList<String> list = new ArrayList<>();
        for (String s : arr) {
            if (!"".equals(s)) {
                list.add(s);
            }
        }
        return list;
    }

    /**
     * 比较新旧操作符的权重,判断是存放还是取出
     * @param s1 新的操作符
     * @param s2 旧的操作符
     * @return 新旧操作符的权重比较
     */
    private static boolean judgeOperator(String s1, String s2) {
        int num1 = 0, num2 = 0;
        switch (s1) {
            case "+":
            case "-":
                num1 = 1;
                break;
            case "*":
            case "/":
                num1 = 2;
                break;
        }
        switch (s2) {
            case "+":
            case "-":
                num2 = 1;
                break;
            case "*":
            case "/":
                num2 = 2;
                break;
        }
        // 判断新旧操作符的优先级
        if (num1 > num2) {
            return true;
        }
        return false;
    }
}

小数算式运算

小数运算要考虑小数点,相对于整数要比较的复杂
在获取娴熟时,需要对小数点的位置进行判断,对小数点右边的数据进行处理

package com.prettyspider.calculate;

import java.util.*;


/**
 * @author prettyspider
 * @ClassName CalcInt
 * @description: 传入整数运算字符串,计算其数值
 * @date 2023/9/11 6:21
 * @Version V1.0
 */

public class CalcDouble {
    /**
     * 中缀表达式转化成后缀表达式
     * <p>
     * 1.遇到操作数直接放入到集合中
     * 2.遇到操作符
     * 2.1当栈为空,或栈顶元素为(,直接放入到栈中
     * 2.2当优先级比栈顶元素高时,直接进栈
     * 2.3当优先级小于等于栈顶元素,将栈顶元素出栈放入到集合中,再和栈顶元素比较
     * 3.遇到左右括号
     * 3.1如果为左括号,直接加入栈
     * 3.2如果为右括号,依次将栈顶元素弹出,直到左括号,并将左括号弹出
     * 4.最后将栈顶元素依次弹出
     */
    public static void main(String[] args) {
        // 要传入的运算字符串
        String s = "10.32*3.23+2.234";
        // 中缀表达式转化成后缀表达式
        List<String> list = inToPastExpression(s);
        // 计算
        double number = calc(list);
        System.out.println("计算的数值为"+number);
    }


    /**
     * 计算后缀表达式
     * @param list 后缀表达式集合
     * @return 传入的整数运算字符串的计算数值
     */
    private static double calc(List<String> list) {
        // 创建栈,用于记录数据
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            // 1.放入 当是数值时,直接放入栈中
            if (s.matches("(\\d|\\.)+")) {
                stack.push(s);
            } else {
                // 2.去除 当是运算符时,再栈中取出两个数,进行运算,并将运算之后的结果放入到栈中
                double num1, num2;
                switch (s) {
                    case "+":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 + num1));
                        break;
                    case "-":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 - num1));
                        break;
                    case "*":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 * num1));
                        break;
                    case "/":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 / num1));
                        break;
                }
            }
        }
        return Double.valueOf(stack.pop());
    }


    /**
     * 将传入的字符串进行切分,存放到集合中
     * @param str 传入的算数字符串
     * @return 后缀表达式集合
     */
    private static List<String> inToPastExpression(String str) {
        // 创建集合和栈
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        // 切分数据
        ArrayList<String> arr = cutString(str);
        for (int i = 0; i < arr.size(); i++) {
            //       * 1.遇到操作数直接放入到集合中
            String value = arr.get(i);
            if (value.matches("(\\d|\\.)+")) {
                list.add(value);
            }
            //      * 3.遇到左右括号
            //      *      3.1如果为左括号,直接加入群
            else if ("(".equals(value)) {
                stack.push(value);
            }
            //      *      3.2如果为右括号,依次将栈顶元素弹出,直到左括号,并将左括号弹出
            else if (")".equals(value)) {
                while (!"(".equals(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.pop();
            }
            //      * 2.遇到操作符
            else {
                //      *      2.1当栈为空,或栈顶元素为(,直接放入到栈中
                //      *      2.3当优先级小于等于栈顶元素,将栈顶元素出栈放入到集合中,再和栈顶元素比较
                while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
                    list.add(stack.pop());
                }
                //      *      2.2当优先级比栈顶元素高时,直接进栈
                stack.push(value);
            }
        }
        //      * 4.最后将栈顶元素依次弹出
        while (!stack.empty()) {
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * 将运算字符切分切分成集合
     * @param str 待切分字符串
     * @return ArrayList<String> 被切分之后的字符串集合
     */
    private static ArrayList<String> cutString(String str) {
        String[] arr = new String[str.length()-1];
        // 为字符串数组赋初值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "";
        }
        int index = 0;
        arr[index] = String.valueOf(str.charAt(0));
        for (int i = 1; i < str.length(); i++) {
            // 1.是数值放入
            if (Character.isDigit(str.charAt(i))|| ".".equals(String.valueOf(str.charAt(i)))) {
                // 1.1并看其起一个数据是不是也数值,是数值,将其前一个数据拼接
                if (arr[index].matches("(\\d|\\.)+")) {
                    arr[index] = arr[index] + str.charAt(i);
                } else {
                    arr[++index] = String.valueOf(str.charAt(i));
                }
            } else {
                // 2.不是数值,直接加入到集合中
                arr[++index] = String.valueOf(str.charAt(i));
            }
        }
        // 去除null
        ArrayList<String> list = removeNull(arr);
        return list;

    }

    /**
     * 将字符串数组中为空的元素去除
     * @param arr 字符串数组
     * @return 去除控制的字符串集合
     */
    private static ArrayList<String> removeNull(String[] arr) {
        ArrayList<String> list = new ArrayList<>();
        for (String s : arr) {
            if (!"".equals(s)) {
                list.add(s);
            }
        }
        return list;
    }

    /**
     * 比较新旧操作符的权重,判断是存放还是取出
     * @param s1 新的操作符
     * @param s2 旧的操作符
     * @return 新旧操作符的权重比较
     */
    private static boolean judgeOperator(String s1, String s2) {
        int num1 = 0, num2 = 0;
        switch (s1) {
            case "+":
            case "-":
                num1 = 1;
                break;
            case "*":
            case "/":
                num1 = 2;
                break;
        }
        switch (s2) {
            case "+":
            case "-":
                num2 = 1;
                break;
            case "*":
            case "/":
                num2 = 2;
                break;
        }
        // 判断新旧操作符的优先级
        if (num1 > num2) {
            return true;
        }
        return false;
    }
}

在获取数据时,巧妙的使用正则获取对应的数据,利于数据的处理

原文链接:https://www.cnblogs.com/prettyspider/p/17703787.html

 友情链接:直通硅谷  点职佳