前言

经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。

描述

输入一个表达式（用字符串表示），求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

数据范围：表达式计算结果和过程中满足 ∣????????????∣≤1000 ∣val∣≤1000  ，字符串长度满足 1≤????≤1000 1≤n≤1000 

输入描述：

输入一个算术表达式

输出描述：

得到计算结果

示例1

输入：

3+2*{1+2*[-4/(8-6)+7]}
输出：

25

实现原理

在 Java 中实现支持负数、大括号、中括号和小括号的四则运算，可以通过以下步骤：

1. 处理括号：将中缀表达式中的大括号 {}, 中括号 [] 和小括号 () 全部转换成统一的小括号 ()。
2. 中缀转后缀：将中缀表达式转换为后缀表达式（RPN）。
3. 计算后缀表达式：使用栈计算后缀表达式的值。

实现代码

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String expression = in.nextLine();
        expression = replaceBrackets(expression);
        List<String> postfix = infixToPostfix(expression);
        int result = evaluatePostfix(postfix);
        System.out.println(result);
    }

    // 判断是否是运算符
    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    // 获取运算符的优先级
    private static int precedence(char c) {
        switch (c) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return -1;
        }
    }

    // 将表达式中的大括号和中括号替换为小括号
    private static String replaceBrackets(String expression) {
        return expression.replace('{', '(')
               .replace('}', ')')
               .replace('[', '(')
               .replace(']', ')');
    }

    // 将中缀表达式转换为后缀表达式
    public static List<String> infixToPostfix(String expression) {
        Stack<Character> stack = new Stack<>();
        List<String> postfix = new ArrayList<>();
        int n = expression.length();

        for (int i = 0; i < n; i++) {
            char c = expression.charAt(i);

            // 如果是数字或者负号开头的数字
            if (Character.isDigit(c) || (c == '-' && (i == 0 ||
                                         expression.charAt(i - 1) == '('))) {
                StringBuilder number = new StringBuilder();
                number.append(c);
                i++;
                while (i < n && Character.isDigit(expression.charAt(i))) {
                    number.append(expression.charAt(i));
                    i++;
                }
                i--;
                postfix.add(number.toString());
            }
            // 左括号
            else if (c == '(') {
                stack.push(c);
            }
            // 右括号
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.add(String.valueOf(stack.pop()));
                }
                stack.pop();
            }
            // 运算符
            else if (isOperator(c)) {
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(c)) {
                    postfix.add(String.valueOf(stack.pop()));
                }
                stack.push(c);
            }
        }

        // 将栈中剩余的运算符添加到后缀表达式
        while (!stack.isEmpty()) {
            postfix.add(String.valueOf(stack.pop()));
        }

        return postfix;
    }

    // 计算逆波兰表达式的值
    public static int evaluatePostfix(List<String> postfix) {
        Stack<Integer> stack = new Stack<>();

        for (String token : postfix) {
            if (isOperator(token.charAt(0)) && token.length() == 1) {
                int b = stack.pop();
                int a = stack.pop();
                switch (token.charAt(0)) {
                    case '+':
                        stack.push(a + b);
                        break;
                    case '-':
                        stack.push(a - b);
                        break;
                    case '*':
                        stack.push(a * b);
                        break;
                    case '/':
                        if (b == 0) {
                            throw new ArithmeticException("除数不能为零");
                        }
                        stack.push(a / b);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

函数说明:

• isOperator 方法：

  • 判断一个字符是否是运算符（+、-、*、/）。

• precedence 方法：

  • 获取运算符的优先级，* 和 / 的优先级高于 + 和 -。

• replaceBrackets 方法：

  • 将表达式中的大括号 {} 和中括号 [] 替换为小括号 ()。

• infixToPostfix 方法：

  • 将中缀表达式转换为后缀表达式。使用栈处理运算符和括号，处理过程中需要特别注意负数的情况。

• evaluatePostfix 方法：

  • 使用栈计算后缀表达式的值。遍历后缀表达式的每个 token，如果是运算符，则从栈中弹出两个操作数进行计算，并将结果压入栈中；如果是数字，则直接压入栈中。

1.QA: