引言
栈（Stack）是一种后进先出（LIFO, Last In First Out）的线性数据结构。它的操作限制在表的一端进行，这一端称为栈顶。栈在计算机科学中应用广泛，从函数调用到表达式求值，从浏览器后退到撤销操作，无处不在。本文将通过中缀表达式转后缀表达式（逆波兰表示法）和计算器求值两个经典场景，深入讲解栈的原理与Java实现。
栈的基本概念
栈支持两种核心操作：
– push：将元素压入栈顶
– pop：将栈顶元素弹出
此外通常还有peek（查看栈顶但不弹出）和isEmpty（判空）等辅助操作。
栈的基础实现
/**
* 基于数组的栈实现
* 支持动态扩容
*/
public class ArrayStack<T> {
private Object[] data;
private int size;
private static final int DEFAULT_CAPACITY = 16;
public ArrayStack() {
this.data = new Object[DEFAULT_CAPACITY];
this.size = 0;
}
/**
* 压栈操作
*/
public void push(T item) {
ensureCapacity();
data[size++] = item;
}
/**
* 弹栈操作
*/
@SuppressWarnings("unchecked")
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T item = (T) data[--size];
data[size] = null; // 防止内存泄漏
return item;
}
/**
* 查看栈顶元素
*/
@SuppressWarnings("unchecked")
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return (T) data[size - 1];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private void ensureCapacity() {
if (size == data.length) {
data = Arrays.copyOf(data, data.length * 2);
}
}
}
中缀表达式转后缀表达式
中缀表达式是我们日常书写的表达式形式，如 3 + 5 * 2。后缀表达式（逆波兰表示法）将运算符放在操作数之后，如 3 5 2 * +。后缀表达式的优点是不需要括号即可明确运算顺序，且便于计算机求值。
转换算法使用栈来处理运算符：
import java.util.*;
/**
* 表达式转换器：中缀转后缀
*/
public class InfixToPostfix {
// 运算符优先级
private static final Map<Character, Integer> PRECEDENCE = new HashMap<>();
static {
PRECEDENCE.put('+', 1);
PRECEDENCE.put('-', 1);
PRECEDENCE.put('*', 2);
PRECEDENCE.put('/', 2);
PRECEDENCE.put('^', 3); // 乘方
}
/**
* 将中缀表达式转换为后缀表达式
* @param infix 中缀表达式，支持 + - * / ^ 和括号
* @return 后缀表达式（以空格分隔）
*/
public static String convert(String infix) {
StringBuilder postfix = new StringBuilder();
ArrayStack<Character> operatorStack = new ArrayStack<>();
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
// 跳过空格
if (ch == ' ') continue;
// 数字或小数点：直接输出
if (Character.isDigit(ch) || ch == '.') {
// 处理多位数
while (i < infix.length() &&
(Character.isDigit(infix.charAt(i)) || infix.charAt(i) == '.')) {
postfix.append(infix.charAt(i));
i++;
}
postfix.append(' ');
i--; // 回退一位，因为for循环会自增
}
// 左括号：压栈
else if (ch == '(') {
operatorStack.push(ch);
}
// 右括号：弹出到左括号
else if (ch == ')') {
while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
postfix.append(operatorStack.pop()).append(' ');
}
if (!operatorStack.isEmpty() && operatorStack.peek() == '(') {
operatorStack.pop(); // 弹出左括号
}
}
// 运算符
else if (isOperator(ch)) {
// 处理负号（一元运算符）
if (ch == '-' && (i == 0 || infix.charAt(i - 1) == '(' || isOperator(infix.charAt(i - 1)))) {
postfix.append(ch); // 将负号与数字合并
} else {
// 弹出优先级大于等于当前运算符的运算符
while (!operatorStack.isEmpty() &&
operatorStack.peek() != '(' &&
precedence(operatorStack.peek()) >= precedence(ch)) {
postfix.append(operatorStack.pop()).append(' ');
}
operatorStack.push(ch);
}
}
}
// 弹出栈中剩余运算符
while (!operatorStack.isEmpty()) {
postfix.append(operatorStack.pop()).append(' ');
}
return postfix.toString().trim();
}
private static boolean isOperator(char ch) {
return PRECEDENCE.containsKey(ch);
}
private static int precedence(char op) {
return PRECEDENCE.getOrDefault(op, 0);
}
}
后缀表达式求值
后缀表达式的求值同样使用栈，过程更为直接：遇到数字压栈，遇到运算符弹出两个操作数计算后将结果压栈。
/**
* 后缀表达式求值器
*/
public class PostfixEvaluator {
/**
* 计算后缀表达式的值
*/
public static double evaluate(String postfix) {
ArrayStack<Double> valueStack = new ArrayStack<>();
String[] tokens = postfix.split("\\s+");
for (String token : tokens) {
if (token.isEmpty()) continue;
if (isNumber(token)) {
valueStack.push(Double.parseDouble(token));
} else if (token.length() == 1 && isOperator(token.charAt(0))) {
// 弹出两个操作数（注意顺序：先弹出的是右操作数）
double b = valueStack.pop();
double a = valueStack.pop();
double result = applyOperator(a, b, token.charAt(0));
valueStack.push(result);
}
}
return valueStack.pop();
}
private static boolean isNumber(String s) {
try {
Double.parseDouble(s);
return true;
} catch (NumberFormatException e) {
return false;
}
}
private static boolean isOperator(char ch) {
return "+-*/^".indexOf(ch) >= 0;
}
private static double applyOperator(double a, double b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/':
if (b == 0) throw new ArithmeticException("除零错误");
return a / b;
case '^': return Math.pow(a, b);
default: throw new IllegalArgumentException("未知运算符: " + op);
}
}
}
完整计算器实现
/**
* 基于栈的完整计算器
* 支持中缀表达式的直接求值
*/
public class StackCalculator {
/**
* 直接计算中缀表达式（双栈法）
* 一个栈存操作数，一个栈存运算符
*/
public static double calculate(String expression) {
ArrayStack<Double> values = new ArrayStack<>();
ArrayStack<Character> ops = new ArrayStack<>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == ' ') continue;
// 数字
if (Character.isDigit(ch) || ch == '.') {
StringBuilder num = new StringBuilder();
while (i < expression.length() &&
(Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
num.append(expression.charAt(i));
i++;
}
values.push(Double.parseDouble(num.toString()));
i--;
}
// 左括号
else if (ch == '(') {
ops.push(ch);
}
// 右括号：计算到左括号
else if (ch == ')') {
while (!ops.isEmpty() && ops.peek() != '(') {
applyTopOperator(values, ops);
}
ops.pop(); // 弹出左括号
}
// 运算符
else if (isOperator(ch)) {
while (!ops.isEmpty() &&
ops.peek() != '(' &&
precedence(ops.peek()) >= precedence(ch)) {
applyTopOperator(values, ops);
}
ops.push(ch);
}
}
// 计算剩余运算符
while (!ops.isEmpty()) {
applyTopOperator(values, ops);
}
return values.pop();
}
private static void applyTopOperator(ArrayStack<Double> values, ArrayStack<Character> ops) {
double b = values.pop();
double a = values.pop();
char op = ops.pop();
values.push(apply(a, b, op));
}
private static double apply(double a, double b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/':
if (b == 0) throw new ArithmeticException("除零错误");
return a / b;
default: throw new IllegalArgumentException("未知运算符");
}
}
private static boolean isOperator(char ch) {
return "+-*/".indexOf(ch) >= 0;
}
private static int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
}
括号匹配检测
栈的另一个经典应用是括号匹配检测：
/**
* 括号匹配检测器
*/
public class BracketMatcher {
private static final Map<Character, Character> PAIRS = new HashMap<>();
static {
PAIRS.put(')', '(');
PAIRS.put('}', '{');
PAIRS.put(']', '[');
}
/**
* 检测字符串中的括号是否匹配
*/
public static boolean isValid(String s) {
ArrayStack<Character> stack = new ArrayStack<>();
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (stack.isEmpty()) return false;
if (stack.pop() != PAIRS.get(ch)) return false;
}
}
return stack.isEmpty();
}
}
主程序与测试
public class StackMain {
public static void main(String[] args) {
// 测试中缀转后缀
String[] testExpressions = {
"3 + 5 * 2",
"(3 + 5) * 2",
"10 - 4 / 2",
"2 ^ 3 + 4 * 5",
"((1 + 2) * 3 - 4) / 5"
};
System.out.println("=== 中缀转后缀 ===");
for (String expr : testExpressions) {
String postfix = InfixToPostfix.convert(expr);
double value = PostfixEvaluator.evaluate(postfix);
System.out.printf("%s -> %s = %.2f%n", expr, postfix, value);
}
// 测试直接计算
System.out.println("\n=== 直接计算 ===");
for (String expr : testExpressions) {
double value = StackCalculator.calculate(expr);
System.out.printf("%s = %.2f%n", expr, value);
}
// 测试括号匹配
System.out.println("\n=== 括号匹配检测 ===");
String[] bracketTests = {"()", "()[]{}", "(]", "([)]", "{[]}", ""};
for (String s : bracketTests) {
System.out.printf("\"%s\" -> %s%n", s, BracketMatcher.isValid(s));
}
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| push/pop/peek | O(1) | O(1) |
| 中缀转后缀 | O(n) | O(n) |
| 后缀求值 | O(n) | O(n) |
| 括号匹配 | O(n) | O(n) |
其中n为表达式长度。
总结
栈的简单LIFO特性使其成为解决”嵌套”和”反转”问题的利器。除了本文介绍的表达式处理，栈还广泛应用于函数调用栈、浏览器前进后退、撤销操作、深度优先搜索等场景。理解栈的本质，有助于在遇到相关问题时快速选择正确的数据结构。
