将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。java

以下是一种 Java 实现：

import java.util.*;

public class ReversePolishNotation {

    public static void main(String[] args) {
        String expression = "3+4*2/(1-5)^2";
        List<String> postfix = infixToPostfix(expression);
        System.out.println("Infix: " + expression);
        System.out.println("Postfix: " + postfix);
        System.out.println("Result: " + evaluatePostfix(postfix));
    }

    public static List<String> infixToPostfix(String expression) {
        List<String> postfix = new ArrayList<>();
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < expression.length()) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                StringBuilder sb = new StringBuilder();
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    sb.append(expression.charAt(i));
                    i++;
                }
                postfix.add(sb.toString());
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(c)) {
                    postfix.add(stack.pop().toString());
                }
                stack.push(c);
                i++;
            } else if (c == '(') {
                stack.push(c);
                i++;
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.add(stack.pop().toString());
                }
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                }
                i++;
            } else {
                i++;
            }
        }
        while (!stack.isEmpty()) {
            postfix.add(stack.pop().toString());
        }
        return postfix;
    }

    public static int evaluatePostfix(List<String> postfix) {
        Stack<Integer> stack = new Stack<>();
        for (String s : postfix) {
            if (Character.isDigit(s.charAt(0))) {
                stack.push(Integer.parseInt(s));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                int result = 0;
                switch (s.charAt(0)) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                    case '^':
                        result = (int) Math.pow(a, b);
                        break;
                }
                stack.push(result);
            }
        }
        return stack.pop();
    }

    private static int precedence(char op) {
        if (op == '+' || op == '-') {
            return 1;
        } else if (op == '*' || op == '/') {
            return 2;
        } else if (op == '^') {
            return 3;
        } else {
            return 0;
        }
    }
}

在这个实现中，我们首先定义了两个方法：

1. `infixToPostfix`：将中缀表达式转换为后缀表达式。
2. `evaluatePostfix`：计算后缀表达式的值。

`infixToPostfix` 方法使用一个栈来解析输入表达式。我们逐个处理输入表达式的字符，如果遇到数字，我们将其添加到后缀表达式列表中。如果遇到运算符，我们将其与栈顶的运算符比较，如果栈顶运算符的优先级大于等于当前运算符，我们就将栈顶运算符弹出并添加到后缀表达式列表中。然后将当前运算符压入栈中。如果遇到左括号，我们将其压入栈中。如果遇到右括号，我们将栈顶元素弹出并添加到后缀表达式列表中，直到遇到左括号。最后，我们将栈中剩余的元素弹出并添加到后缀表达式列表中。

`evaluatePostfix` 方法使用一个栈来计算后缀表达式。我们逐个处理后缀表达式中的元素，如果遇到数字，我们将其压入栈中。如果遇到运算符，我们就从栈中弹出两个元素，进行相应的运算，并将结果压入栈中。最后，栈中剩下的元素就是表达式的值。

这个实现的时间复杂度是 O(n)，其中 n 是表达式的长度。