Java栈的应用

Java中的栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。Java提供了java.util.Stack类，该类能够在程序中实现栈的功能。在Java中，栈有多种应用，以下是一些常见的应用场景：

`Stack` 类的基本用法

导入 Stack 类: java.util.Stack
创建 Stack 实例
使用 push() 方法添加元素
使用 pop() 方法移除并返回栈顶元素

示例代码

下面是一个简单的示例，演示如何使用 pop() 方法来从栈中移除元素：

import java.util.Stack;  public class StackExample {  public static void main(String[] args) {  // 创建一个栈实例  Stack<Integer> stack = new Stack<>();  // 入栈操作  stack.push(1);  stack.push(2);  stack.push(3);  System.out.println("当前栈: " + stack);  // 弹栈操作  System.out.println("弹出栈顶元素: " + stack.pop()); // 返回 3  System.out.println("当前栈: " + stack);  System.out.println("弹出栈顶元素: " + stack.pop()); // 返回 2  System.out.println("当前栈: " + stack);  System.out.println("弹出栈顶元素: " + stack.pop()); // 返回 1  System.out.println("当前栈: " + stack);  // 测试弹出空栈的情况  try {  stack.pop(); // 此时栈是空的，应该抛出 EmptyStackException  } catch (Exception e) {  System.out.println("异常: " + e);  }  }  
}

表达式求值

利用栈将中缀表达式转换为后缀表达式并求值：

1. `main` 方法

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

输入表达式：定义了一个中缀格式的数学表达式字符串。
输出原表达式：打印出输入的中缀表达式。
结果输出：调用 evaluateExpression 方法计算表达式的值并打印结果。

2. evaluateExpression 方法

public static double evaluateExpression(String expression) {  List<String> postfix = infixToPostfix(expression);  return evaluatePostfix(postfix);  
}

将中缀转换为后缀：调用 infixToPostfix 方法将中缀表达式转换为后缀表达式。
评估后缀表达式：调用 evaluatePostfix 方法计算后缀表达式的值并返回结果。

3. `infixToPostfix` 方法

private static List<String> infixToPostfix(String expression) {  Stack<String> stack = new Stack<>();  List<String> output = new ArrayList<>();  String[] tokens = expression.split(" ");  for (String token : tokens) {  if (isNumber(token)) {  output.add(token);  } else if (token.equals("(")) {  stack.push(token);  } else if (token.equals(")")) {  while (!stack.isEmpty() && !stack.peek().equals("(")) {  output.add(stack.pop());  }  stack.pop();  } else {  while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(token)) {  output.add(stack.pop());  }  stack.push(token);  }  }  while (!stack.isEmpty()) {  output.add(stack.pop());  }  return output;  
}

输入分解：将中缀表达式按空格拆分成 tokens。
处理每个 token：
- 数字：如果 token 是数字，则将其添加到输出列表。
- 左括号 (：将其压入栈中。
- 右括号 )：连续弹出栈中的操作符直到遇到左括号。
- 操作符：根据优先级弹出栈中的操作符并将其添加到输出列表，然后将当前操作符压入栈。
最终处理：将栈中剩余的操作符全部弹出，形成完整的后缀表达式并返回。

4. `evaluatePostfix` 方法

private static double evaluatePostfix(List<String> postfix) {  Stack<Double> stack = new Stack<>();  for (String token : postfix) {  if (isNumber(token)) {  stack.push(Double.parseDouble(token));  } else {  double b = stack.pop();  double a = stack.pop();  stack.push(applyOperation(a, b, token));  }  }  return stack.pop();  
}

评估后缀表达式：逐个处理后缀表达式中的每个 token。
- 数字：将数字解析并压入栈中。
- 操作符：从栈中弹出两个数字（b 和 a），计算结果，并将结果推入栈中。
返回结果：最终，栈中只会剩下一个元素，就是表达式的计算结果。

5. `isNumber` 方法

private static boolean isNumber(String token) {  try {  Double.parseDouble(token);  return true;  } catch (NumberFormatException e) {  return false;  }  
}

判断字符串是否为数字：尝试将 token 转换为 double。如果成功则返回 true，否则返回 false。
6. precedence 方法

private static int precedence(String op) {  switch (op) {  case "+": case "-": return 1;  case "*": case "/": return 2;  case "^": return 3;  default: return 0;  }  
}

获取操作符的优先级：不同的操作符有不同的优先级（如 + 和 - 的优先级低于 * 和 /，而 ^ 的优先级最高）

7. applyOperation 方法

private static double applyOperation(double a, double b, String op) {  switch (op) {  case "+": return a + b;  case "-": return a - b;  case "*": return a * b;  case "/": return a / b;  case "^": return Math.pow(a, b);  default: throw new UnsupportedOperationException("Invalid operator: " + op);  }  
}

执行基本运算：根据传入的操作符执行相应的数学运算并返回结果。

完整代码:

import java.util.*;  public class ExpressionEvaluator {  public static void main(String[] args) {  String expression = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";  System.out.println("Infix expression: " + expression);  System.out.println("Result: " + evaluateExpression(expression));  }  public static double evaluateExpression(String expression) {  List<String> postfix = infixToPostfix(expression);  return evaluatePostfix(postfix);  }  private static List<String> infixToPostfix(String expression) {  Stack<String> stack = new Stack<>();  List<String> output = new ArrayList<>();  String[] tokens = expression.split(" ");  for (String token : tokens) {  if (isNumber(token)) {  output.add(token);  } else if (token.equals("(")) {  stack.push(token);  } else if (token.equals(")")) {  while (!stack.isEmpty() && !stack.peek().equals("(")) {  output.add(stack.pop());  }  stack.pop();  } else {  while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(token)) {  output.add(stack.pop());  }  stack.push(token);  }  }  while (!stack.isEmpty()) {  output.add(stack.pop());  }  return output;  }  private static double evaluatePostfix(List<String> postfix) {  Stack<Double> stack = new Stack<>();  for (String token : postfix) {  if (isNumber(token)) {  stack.push(Double.parseDouble(token));  } else {  double b = stack.pop();  double a = stack.pop();  stack.push(applyOperation(a, b, token));  }  }  return stack.pop();  }  private static boolean isNumber(String token) {  try {  Double.parseDouble(token);  return true;  } catch (NumberFormatException e) {  return false;  }  }  private static int precedence(String op) {  switch (op) {  case "+": case "-": return 1;  case "*": case "/": return 2;  case "^": return 3;  default: return 0;  }  }  private static double applyOperation(double a, double b, String op) {  switch (op) {  case "+": return a + b;  case "-": return a - b;  case "*": return a * b;  case "/": return a / b;  case "^": return Math.pow(a, b);  default: throw new UnsupportedOperationException("Invalid operator: " + op);  }  }  
}