[Java知识库]逆波兰表达式实现计算器----Java

逆波兰表达式就是后缀表达式，比如正常表达式（也就是中缀表达式）是"300+5*((6- 3)-2)"的一个字符串，那么它的后缀表达式形式是[300, 5, 6, 3, -, 2, -, *, +]（这里我就直接用集合的形式来表达）。用中缀表达式计算算式时，我们需要考虑优先级问题，如果没有小括号，问题就很简单，可这样功能较单一。而后缀表达式不需要考虑优先级问题，关键就放在了中缀表达式转换成后缀表达式，这里有笔者写的代码可供参考。

package com.stack;

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

//这里运用逆波兰表达式实现计算器功能
//支持+ - * / ()
//支持多位数。小数
//兼容处理，过滤空白字符、制表符、换页符

public class RPNCalculate {
    public static void main(String[] args) {
        String s = "  300+5*((6- 3) - 2)";//如果需要输入的话可自行添加
        List<String> infixList = ToInfixExpressionList(s);
        List<String> suffixList = parseSuffixExpressionList(infixList);
        System.out.println(suffixList);//[300, 5, 6, 3, -, 2, -, *, +]
        System.out.println(calculate(suffixList));
    }

    //将中缀表达式形式的字符串转换成中缀表达式形式的集合
    public static List<String> ToInfixExpressionList(String expression) {
        expression = expression.replaceAll("\\s+", "");//去除空白字符、制表符、换页符
        int index = 0;//索引
        char c;//存储每次取出的字符
        int len = expression.length();//字符串长度
        String str;//拼接多位数字
        List<String> list = new ArrayList<>();
        do {
            c = expression.charAt(index);
            //判断是否为数字
            if ((c + "").matches("\\d+")) {
                str = "";//初始化
                while (index < len && ((c = expression.charAt(index)) + "").matches("\\d+")) {
                    str += c;
                    index++;
                }
                list.add(str);
            } else {
                //如果不是数字则直接加入集合
                list.add("" + c);
                index++;
            }
        } while (index < len);
        return list;
    }

    //将中缀表达式集合转变成后缀表达式集合
    public static List<String> parseSuffixExpressionList(List<String> infixList) {
        Stack<String> stack = new Stack<>();//转换时放运算符
        List<String> list = new ArrayList<>();
        //遍历
        for (String s : infixList) {
            if (s.matches("\\d+"))//如果是数字直接存入集合
                list.add(s);
            else if (s.equals("("))//如果是"(",先存入栈中
                stack.push(s);
            else if (s.equals(")")) {//如果是")",则把栈中的运算符依次放入集合中，直到"("
                while (!stack.peek().equals("("))
                    list.add(stack.pop());
                stack.pop();
            } else {
                //循环判断s的优先级是否比栈顶的优先级低,成立就把栈顶的运算符拿出放到集合中
                while (stack.size() != 0 && operation(s) <= operation(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.push(s);
            }
        }
        //将stack中剩余的运算符放到集合中
        while (stack.size() != 0)
            list.add(stack.pop());

        return list;
    }

    //逆波兰表达式的计算
    public static float calculate(List<String> list){
        Stack<Float> stack=new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+"))
                stack.push(Float.valueOf(s));
            else {
                float num2=stack.pop();
                float num1=stack.pop();
                switch (s){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                    default:
                        break;
                }
            }
        }
        return stack.pop();
    }

    //判断运算符的优先级，返回的数越大，运算级越高
    public static int operation(String s) {
        switch (s) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            case "(":
                return 0;
            default:
                throw new RuntimeException(s + "不是运算符,请重新输入!");
        }
    }
}

万分感谢大家的阅读，有不足的地方希望大家可以指出。