主页 > 游戏开发 >

蓝桥杯JavaB组之栈的应用（括号匹配、表达式求值）

游戏开发
2025-09-08 02:24:02

一、栈的基本概念

栈（Stack）是一种特殊的线性数据结构，遵循后进先出（Last In First Out，LIFO）的原则。就像一摞盘子，最后放上去的盘子总是最先被拿走。栈有两个主要操作：

入栈（Push）：将一个元素添加到栈的顶部。

出栈（Pop）：移除并返回栈顶部的元素。

二、手写栈的实现

java

class MyStack { private int[] array; // 用于存储栈中的元素 private int top; // 栈顶指针，指向栈顶元素的索引 private int capacity; // 栈的容量 // 构造函数，初始化栈的容量 public MyStack(int capacity) { this.capacity = capacity; this.array = new int[capacity]; this.top = 1; // 初始时栈为空，栈顶指针为 1 } // 判断栈是否为空 public boolean isEmpty() { return top == 1; } // 判断栈是否已满 public boolean isFull() { return top == capacity 1; } // 入栈操作 public void push(int element) { if (isFull()) { System.out.println("栈已满，无法入栈"); return; } array[++top] = element; // 先将栈顶指针加 1，再将元素放入栈顶 } // 出栈操作 public int pop() { if (isEmpty()) { System.out.println("栈为空，无法出栈"); return 1; } return array[top ]; // 先返回栈顶元素，再将栈顶指针减 1 } // 获取栈顶元素 public int peek() { if (isEmpty()) { System.out.println("栈为空，没有栈顶元素"); return 1; } return array[top]; } }

三、栈的应用

1. 有效的括号

问题描述：给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

思路：遍历字符串，遇到左括号就将其入栈，遇到右括号就检查栈顶元素是否为对应的左括号，如果是则出栈，否则字符串无效。遍历结束后，如果栈为空，则字符串有效。

java

import java.util.Stack; public class ValidParentheses { public static boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '{' || c == '[') { stack.push(c); // 遇到左括号，入栈 } else { if (stack.isEmpty()) { return false; // 栈为空，遇到右括号，无效 } char top = stack.pop(); // 出栈栈顶元素 if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) { return false; // 括号不匹配，无效 } } } return stack.isEmpty(); // 栈为空则有效 } public static void main(String[] args) { String s = "()[]{}"; System.out.println(isValid(s)); } }

2. 逆波兰表达式求值

问题描述：逆波兰表达式（后缀表达式）是一种数学表达式的表示方法，其中运算符紧跟在操作数之后。给定一个逆波兰表达式，求其值。

思路：遍历逆波兰表达式，遇到操作数就入栈，遇到运算符就从栈中弹出两个操作数进行运算，再将结果入栈。遍历结束后，栈中剩下的元素就是表达式的值。

java

import java.util.Stack; public class EvaluateReversePolishNotation { public static int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String token : tokens) { if (isOperator(token)) { int operand2 = stack.pop(); // 弹出第二个操作数 int operand1 = stack.pop(); // 弹出第一个操作数 int result = applyOperation(operand1, operand2, token); // 进行运算 stack.push(result); // 将结果入栈 } else { stack.push(Integer.parseInt(token)); // 遇到操作数，入栈 } } return stack.pop(); // 栈中剩下的元素就是表达式的值 } // 判断是否为运算符 private static boolean isOperator(String token) { return token.equals("+") || token.equals(" ") || token.equals("*") || token.equals("/"); } // 进行运算 private static int applyOperation(int operand1, int operand2, String operator) { switch (operator) { case "+": return operand1 + operand2; case " ": return operand1 operand2; case "*": return operand1 * operand2; case "/": return operand1 / operand2; default: return 0; } } public static void main(String[] args) { String[] tokens = {"2", "1", "+", "3", "*"}; System.out.println(evalRPN(tokens)); } }

练习1：中缀转后缀表达式

规则：

操作数直接输出。

运算符与栈顶比较优先级，优先级高则入栈，否则弹出栈顶。

左括号入栈，右括号弹出直到左括号。

public String infixToPostfix(String infix) { MyStack<Character> stack = new MyStack<>(); StringBuilder postfix = new StringBuilder(); for (char c : infix.toCharArray()) { if (Character.isDigit(c)) { postfix.append(c); } else if (c == '(') { stack.push(c); } else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') { postfix.append(stack.pop()); } stack.pop(); // 弹出左括号 } else { while (!stack.isEmpty() && priority(c) <= priority(stack.peek())) { postfix.append(stack.pop()); } stack.push(c); } } while (!stack.isEmpty()) postfix.append(stack.pop()); return postfix.toString(); }

蓝桥杯中的常考点和易错点

常考点：

栈的基本操作：push、pop、peek、isEmpty。

括号匹配：使用栈检查括号是否正确匹配。

逆波兰表达式求值：使用栈计算逆波兰表达式的值。

数据结构的实现：手写栈的实现，理解其内部机制。

易错点：

栈的边界条件：容易忽略栈为空或栈满的情况，导致运行时错误。

括号匹配的逻辑：容易在处理右括号时忘记检查栈是否为空。

逆波兰表达式的操作符处理：容易在计算时混淆操作数的顺序，尤其是减法和除法。

数组越界：在实现栈时，容易因为数组越界而出现错误。

6. 相关知识点总结