逆波兰表达式计算器

逆波兰表达式计算器

先看效果

实现过程

1. 将算式解析为中缀表达式
2. 将中缀表达式转换为后缀表达式
3. 计算

中缀表达式

什么是中缀表达式？
	中缀表达式是一种数学表达式的书写方式，指的是运算符位于操作数之间的表达式。
	直白一点讲,例如:"(3+4)*5",这个就是中缀表达式

后缀表达式

什么是后缀表达式？
	后缀表达式（也叫做逆波兰式）：运算符位于操作数之后，例如"3 4 +"表示加法运算3和4，	计算结果为7。

中缀表达式转后缀表达式

[(, (, 100, +, 101, ), +, (, 102, +, 103, ), ), *, 104, +, 105]

算式转中缀表达式咱们就不细说怎么做了，这个太基础了。

中缀表达式转后缀表达式。
使用一个list，stack和map。
list用于存放最终的表达式的元素，
stack用于临时存放运算符和数值，
map中初始化四个运算符，key为运算符，value为优先级，“*”,“/“的优先级为2，”+”,"-"的优先级为1

接下来直接看代码吧

转换结果：

[100, 101, +, 102, 103, +, +, 104, *, 105, +]

List<String> infixExpression = Arrays.asList("(", "(", "100", "+", "101", ")", "+", "(", "102", "+", "103", ")", ")", "*", "104","+","105");
List<String> rpnExpression = convertToRPN(infixExpression);

public static List<String> convertToRPN(List<String> infixExpression) {
        Map<String, Integer> precedence = new HashMap<>(); // 初始化四个运算符，并配置优先级
        precedence.put("+", 1);
        precedence.put("-", 1);
        precedence.put("*", 2);
        precedence.put("/", 2);

        Stack<String> operatorStack = new Stack<>();
        List<String> output = new ArrayList<>();

        for (String token : infixExpression) {
            if (isNumber(token)) {
                output.add(token);
            } else if (token.equals("(")) {
                operatorStack.push(token);
            } else if (token.equals(")")) {
                while (!operatorStack.isEmpty() && !operatorStack.peek().equals("(")) {
                    output.add(operatorStack.pop());
                }
                operatorStack.pop(); // 弹出左括号
            } else if (isOperator(token)) {
                while (!operatorStack.isEmpty() && precedence.getOrDefault(operatorStack.peek(), 0) >= precedence.get(token)) {
                    output.add(operatorStack.pop());
                }
                operatorStack.push(token);
            }
        }

        while (!operatorStack.isEmpty()) {
            output.add(operatorStack.pop());
        }

        return output;
    }


public static boolean isNumber(String token) {
    return token.matches("\\d+");
}

public static boolean isOperator(String token) {
    return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
}

使用后缀表达式计算出结果

List<String> rpnExpression = convertToRPN(infixExpression);

int result = evaluateRPN(rpnExpression);

public static int evaluateRPN(List<String> rpnExpression) {
        Stack<Integer> stack = new Stack<>();

        for (String token : rpnExpression) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else if (isOperator(token)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = evaluate(operand1, operand2, token);
                stack.push(result);
            }
        }

        return stack.pop();
    }

    public static int evaluate(int operand1, int operand2, String operator) {
        switch (operator) {
            case "+":
                return operand1 + operand2;
            case "-":
                return operand1 - operand2;
            case "*":
                return operand1 * operand2;
            case "/":
                return operand1 / operand2;
            default:
                throw new IllegalArgumentException("Unknown operator: " + operator);
        }
    }

完整代码

package com.tfxing.persondaily;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> infixExpression = Arrays.asList("(", "(", "100", "+", "101", ")", "+", "(", "102", "+", "103", ")", ")", "*", "104","+","105");
        System.out.println(infixExpression);
        List<String> rpnExpression = convertToRPN(infixExpression);
        System.out.println(rpnExpression);
        int result = evaluateRPN(rpnExpression);
        System.out.println(result);
    }

    public static List<String> convertToRPN(List<String> infixExpression) {
        Map<String, Integer> precedence = new HashMap<>();
        precedence.put("+", 1);
        precedence.put("-", 1);
        precedence.put("*", 2);
        precedence.put("/", 2);

        Stack<String> operatorStack = new Stack<>();
        List<String> output = new ArrayList<>();

        for (String token : infixExpression) {
            if (isNumber(token)) {
                output.add(token);
            } else if (token.equals("(")) {
                operatorStack.push(token);
            } else if (token.equals(")")) {
                while (!operatorStack.isEmpty() && !operatorStack.peek().equals("(")) {
                    output.add(operatorStack.pop());
                }
                operatorStack.pop(); // 弹出左括号
            } else if (isOperator(token)) {
                while (!operatorStack.isEmpty() && precedence.getOrDefault(operatorStack.peek(), 0) >= precedence.get(token)) {
                    output.add(operatorStack.pop());
                }
                operatorStack.push(token);
            }
        }

        while (!operatorStack.isEmpty()) {
            output.add(operatorStack.pop());
        }

        return output;
    }

    public static boolean isNumber(String token) {
        return token.matches("\\d+");
    }

    public static boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    public static int evaluateRPN(List<String> rpnExpression) {
        Stack<Integer> stack = new Stack<>();

        for (String token : rpnExpression) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else if (isOperator(token)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = evaluate(operand1, operand2, token);
                stack.push(result);
            }
        }

        return stack.pop();
    }

    public static int evaluate(int operand1, int operand2, String operator) {
        switch (operator) {
            case "+":
                return operand1 + operand2;
            case "-":
                return operand1 - operand2;
            case "*":
                return operand1 * operand2;
            case "/":
                return operand1 / operand2;
            default:
                throw new IllegalArgumentException("Unknown operator: " + operator);
        }
    }

}