栈算术表达式JAVA

### 使用 Java 实现基于栈的算术表达式计算

#### 将中缀表达式转换为后缀表达式
为了便于计算机处理，通常会先将常见的中缀表达式（操作符位于两个操作数之间）转化为后缀表达式（逆波兰表示法）。转化过程中可以利用栈来管理运算符优先级。

public class InfixToPostfix {
    private static final String OPERATORS = "+-*/";
    
    public static boolean isOperator(char c){
        return OPERATORS.indexOf(c)!=-1;
    }

    public static int precedence(String op) {
        switch(op.charAt(0)){
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            default : return -1;
        }
    }

    public static String infixToPostfix(String expression) {
        StringBuilder result = new StringBuilder();
        Deque<String> stack = new ArrayDeque<>();
        
        for(int i=0;i<expression.length();++i){
            char ch = expression.charAt(i);
            
            if(Character.isWhitespace(ch)) continue;

            if(Character.isLetterOrDigit(ch))
                result.append(ch); // 如果是字母或数字，则直接加入结果
            
            else if(isOperator(ch)){ 
                while(!stack.isEmpty() && precedence(stack.peek()) >= precedence(String.valueOf(ch)))
                    result.append(' ').append(stack.pop());
                
                stack.push(String.valueOf(ch));
            } 
            
            else if(ch=='(')
                stack.push(String.valueOf(ch)); // 左括号入栈
                
            else if(ch==')'){
                while(!stack.isEmpty() && !stack.peek().equals("("))
                    result.append(' ').append(stack.pop()); // 右括号则弹出直到遇到左括号
                
                stack.pop(); // 移除左括号
            }
            
            if(Character.isLetterOrDigit(ch) && (i+1)<expression.length() && Character.isWhitespace(expression.charAt(i+1))){
                ++i;continue;
            }
            
            if((Character.isLetterOrDigit(ch)||isOperator(ch))&&i!=expression.length()-1)
                result.append(' ');
        }
        
        while (!stack.isEmpty())
            result.append(' ').append(stack.pop());

        return result.toString();
    }
}

此部分代码实现了从中缀到后缀表达式的转换逻辑[^2]。

#### 后缀表达式的求值过程
一旦获得了后缀表达式之后，就可以使用另一个栈来进行实际数值上的计算：

import java.util.*;

public class PostfixEvaluator {

    public static double evaluatePostfixExpression(String exp) throws Exception{
        Stack<Double> values = new Stack<>();

        StringTokenizer tokens = new StringTokenizer(exp);

        while(tokens.hasMoreTokens()){
            String token=tokens.nextToken();

            if(token.matches("[+-]?\\d+(\\.\\d+)?")){ // 数字正则匹配
                values.push(Double.parseDouble(token));
            }else if(InfixToPostfix.isOperator(token.charAt(0))) { // 运算符检测
                Double operand2 = values.pop();
                Double operand1 = values.pop();
                double res = applyOperation(token,operand1,operand2);
                values.push(res);
            } else throw new Exception("Invalid Token");
        }

        return values.empty()?Double.NaN:values.pop();
    }

    private static double applyOperation(String operator,double a,double b)throws ArithmeticException{
        switch(operator){
            case "+" :
                return a+b;
            case "-" :
                return a-b;
            case "*" :
                return a*b;
            case "/" :
                if(b == 0)throw new ArithmeticException("/ by zero.");
                return a/b;
            default:
                throw new IllegalArgumentException("Unexpected value: " + operator);
        }
    }
}

上述代码展示了如何解析并评估由`infixToPostfix()`方法产生的字符串形式的后缀表达式。这里同样运用到了栈的数据结构来存储临时的操作数，并按照相应的运算符执行对应的数学运算[^3]。