逆波兰表达式

import com.sun.deploy.util.StringUtils;

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

/**
 * @author chenyi
 * @Description 逆波兰表达式
 * @date 2022/2/10 10:18
 */
public class PolandNotation {

    /**
     * 将中缀表达式转为后缀表达式
     * @param prefixExpression 中缀表达式
     * @return 后缀表达式
     */
    public static String getSuffixExpression(String prefixExpression) {
        // 数值栈
        Stack<String> numStack = new Stack<>();
        // 运算符栈
        Stack<String> operatorStack = new Stack<>();

        if(prefixExpression.startsWith("-")){
            numStack.push("0");
        }
        // 循环表达式的每一个字符
        for (int i = 0; i < prefixExpression.length(); i++) {
            char c = prefixExpression.charAt(i);
            if(c>='0' && c<='9') {
                // 数值直接入栈
                int j = i;
                while(i+1 < prefixExpression.length()) {
                    if(prefixExpression.charAt(i+1)>='0' && prefixExpression.charAt(i+1)<='9'){
                        i++;
                    } else {
                        break;
                    }
                }
                numStack.push(prefixExpression.substring(j,i+1));
            } else if(c=='(') {
                // 左括号直接入栈
                operatorStack.push(String.valueOf(c));
            } else if(c==')') {
                // 如果是有括号，需要从运算符栈中取出到最近的一个左括号之间的运算符放入数值栈中。最近的一个左括号被移除
                while (!"(".equals(operatorStack.peek())) {
                    numStack.push(operatorStack.pop());
                }
                operatorStack.pop();
            } else {
                // + - x \ 运算符
                // 如果符号栈是空的或者栈顶是左括号则直接写入
                if(operatorStack.empty() || "(".equals(operatorStack.peek())) {
                    operatorStack.push(String.valueOf(c));
                }else{
                    // 如果符号优先级，比栈顶的低。需要把栈顶的符号取出，一直到栈顶的符号不低于当前符号
                    while(!operatorStack.empty()) {
                        int priority1 = "x".equals(operatorStack.peek())||"/".equals(operatorStack.peek())?1:0;
                        int priority2 = 'x'==c||'/'==c ? 1:0;
                        if(priority2>priority1){
                            break;
                        }
                        numStack.push(operatorStack.pop());
                    }
                    operatorStack.push(String.valueOf(c));
                }
            }
        }
        // 将符号栈的符号全部移动到数值栈中
        while(!operatorStack.empty()) {
            numStack.push(operatorStack.pop());
        }
        // 此时数值栈中的依次取出的数据就是逆波兰表达式的倒序，使用list来做翻转
        List<String> list = new ArrayList<>();
        while(!numStack.empty()) {
            list.add(0, numStack.pop());
        }
        return StringUtils.join(list, " ");
    }

    public static Integer calculate(String suffixExpression) {
        String[] elements = suffixExpression.split(" ");
        Stack<Integer> stack = new Stack<>();
        for (String element : elements) {
            if(element.matches("\\d+")) {
                stack.push(Integer.parseInt(element));
            } else {
                int result;
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (element) {
                    case "+":
                        result = num1+num2;
                        break;
                    case "-":
                        result = num1-num2;
                        break;
                    case "x":
                        result = num1*num2;
                        break;
                    case "/":
                        result = num1/num2;
                        break;
                    default:
                        throw new RuntimeException("超出预期的预算符"+element);
                }
                stack.push(result);
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String prefixExpression = "-3-3x3-2";
        String suffixExpression = getSuffixExpression(prefixExpression);
        System.out.println("后缀表达式 = "+suffixExpression);
        Integer calculateResult = calculate(suffixExpression);
        System.out.println("计算后的结果"+calculateResult);
    }


}