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

  一、栈的基本概念

栈（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. 相关知识点总结

栈的实现：使用数组或链表实现栈的基本操作。

括号匹配：通过栈检查括号是否正确匹配。

逆波兰表达式求值：通过栈计算逆波兰表达式的值。

蓝桥杯常考点：栈的基本操作、括号匹配、逆波兰表达式求值。

易错点：栈的边界条件、括号匹配的逻辑、逆波兰表达式的操作符处理。

  四、知识点总结

     栈的特性  ：后进先出（LIFO），适用于需要处理最近发生的元素的场景。

     栈的基本操作  ：入栈（Push）、出栈（Pop）、获取栈顶元素（Peek）、判断栈空（isEmpty）和栈满（isFull）。

     栈的应用场景  ：括号匹配、表达式求值等。在括号匹配中，利用栈来检查括号的闭合顺序；在表达式求值中，使用栈来处理操作数和运算符的运算顺序。

  五、蓝桥杯常考点

     栈的基本操作实现  ：可能要求选手手写栈的实现，包括入栈、出栈等操作。

     栈的应用问题  ：如括号匹配、表达式求值等经典问题，考查选手对栈的理解和应用能力。

     复杂度分析  ：要求分析栈操作和相关算法的时间复杂度和空间复杂度。

  六、蓝桥杯易错点

     栈的边界条件处理  ：在入栈和出栈操作时，要注意栈空和栈满的情况，避免出现数组越界等错误。

     运算符优先级问题  ：在表达式求值中，要正确处理运算符的优先级，确保运算顺序正确。

     数据类型转换  ：在处理逆波兰表达式求值时，要注意将字符串转换为合适的数据类型进行运算。