算法—四则运算

描述

输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

数据范围：表达式计算结果和过程中满足
输入描述：
输入一个算术表达式

输出描述：
得到计算结果

代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        //问题3:括号问题,计算的先后顺序
        s = s.replace("{", "(");
        s = s.replace("[", "(");
        s = s.replace("}", ")");
        s = s.replace("]", ")");
        //1+(8*2-1+3)
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //问题1:第一个数字与(数字,数字为负数的处理 将负数拼接 eg:-3+2*{1+2*[-4/(8-6)+7]}     (0-3)+2*(1+2*((0-4)/(8-6)+7))
            if (c == '-' && (i == 0 || (i > 1 && s.charAt(i - 1) == '('))) {
                stringBuilder.append("(0" + s.charAt(i) + "" + s.charAt(i + 1) + ")");
                i += 1;
            } else {
                stringBuilder.append(c);
            }
        }

        int result = handled(stringBuilder.toString());
        System.out.println(result);
    }

    private static int handled(String s) {
        Stack<Integer> numStack = new Stack<>();//数字栈
        Stack<Character> characterStack = new Stack<>();//字符栈
        int count = 0;//记录当前字符是否是大于10的数字
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                if (!numStack.isEmpty()&&count + 1 == i) {
                    Integer pop = numStack.pop();
                    numStack.push(Integer.valueOf(pop + "" + c));

                } else {
                    count = i;
                    numStack.push(Integer.valueOf(c + ""));
                }
            } else if (c == '(') {
                characterStack.push(c);
            } else if (c == ')') {
                while (!characterStack.isEmpty() && characterStack.peek() != '(') {
                    calcute(characterStack, numStack);
                }
                characterStack.pop();//弹出'('
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                //问题2:四则运算顺序,先乘除后加减
                //问题4:使用栈存储数字时计算应从左向右 否则会出现:3*5+8-0*3-6+0+0 15+8-0-6+0+0=29情况
                while (!characterStack.isEmpty() &&
                        getPrecedence(characterStack.peek()) >= getPrecedence(c)) {
                    calcute(characterStack, numStack);
                }
                characterStack.push(c);
            }
        }
        //计算剩余非括号内的算式
        while (!characterStack.isEmpty()) {
            calcute(characterStack, numStack);
        }

        return numStack.pop(); // 返回最终计算结果
    }

    // 获取运算符的优先级
    public static int getPrecedence(char operator) {
        switch (operator) {
            case ')':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
        }
        return 0;
    }

    //进行计算
    public static void calcute(Stack<Character> characterStack,
                               Stack<Integer> numStack) {
        Integer a = numStack.pop();//先进后出,注意顺序
        Integer b = numStack.pop();
        Character operate = characterStack.pop();
        int result = 0;

        switch (operate) {
            case '-':
                result = b - a;
                break;
            case '+':
                result = b + a;
                break;
            case '*':
                result = b * a;
                break;
            case '/':
                result = b / a;
                break;
        }
        numStack.push(result);
    }
}