共计 2005 个字符,预计需要花费 6 分钟才能阅读完成。
有效的括号
编写程序时, 一个类, 函数, 表达式, 都需要括号匹配, 如果括号没有正确匹配, 编译器就会报错, 这其实一种是数据结构 – 栈的应用.
栈(Stack)
是一种线性结构
只能从一端添加元素, 也只能从同一端取出元素, 这一端称为 栈顶
后进先出的特性(LIFO-last in first out
): 最后插入的元素最先出来.
这种后进先出的特性十分有用, 便于理解栈的实际应用, 举如下两个例子:
-
无处不在的 Undo 操作 (撤销)
编辑器中的撤销原理就是运用了栈先进后出的特性, 栈顶存放了你最近一次的操作, 撤销会将这次操作的内容弹出栈顶 -
程序调用的系统栈
程序在进行子过程调用的时候, 当一个子过程执行完成之后, 可以自动的回到上层调用中断的位置继续执行下去
- 函数 A()在执行到第 2 行时调用了函数 B(),
栈中记录下 A2(表示函数 A()在第 2 行时中断); - 进入函数 B(), 执行到第 2 行时调用函数 C(),
栈中记录下 B2(表示函数 B()在第 2 行时中断); - 进入函数 C()一直到执行完毕,cpu 不知道下一步该执行哪行代码, 到系统栈中查看, 最近一次中断的地方是函数 B()第 2 行, 返回去执行, 到函数 A()也是如此, 执行完毕.
下面说说括号匹配的题目
leetcode 有这样一题, 我们可以参照它来理解这个概念
leetcode 第 20 题: 有效的括号
题目:
给定一个只包括 '(',')','{','}','[',']'
的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
来源:力扣 (LeetCode)
首先声明一个栈,
然后逐一遍历这个括号字符串, 如果是左括号就将它压入栈;
如果是右括号, 此时查看栈顶的元素是否与之匹配, 如果匹配成功, 栈顶的元素就要出栈;
如果最后栈中的元素被清空, 证明这串括号是有效的;
如果匹配失败, 那么就证明了这串括号是错误的.
栈顶元素反应了在嵌套的层次关系中,最近的 需要匹配的元素
标准答案代码实现:
import java.util.HashMap;
import java.util.Stack;
// 有效的括号
public class Solution {
// 负责映射的哈希表
private HashMap<Character,Character> mappings;
// 构造时初始化哈希表, 使代码更具可读性
public Solution(){this.mappings = new HashMap<>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s){
// 声明一个栈
Stack<Character> stack = new Stack<>();
// 遍历字符串
for (int i = 0; i < s.length(); i++){char c = s.charAt(i);
// 如果当前字符串是右括号
if (this.mappings.containsKey(c)){
// 获取栈的顶部元素。如果栈是空的,设置一个哑值 '#'
char topElement = stack.empty() ? '#' : stack.pop();
// 如果此括号的映射与栈的顶部元素不匹配,则返回 false。if (topElement != this.mappings.get(c)){return false;}
}else {
// 如果当前字符是左括号,push 到栈中
stack.push(c);
}
}
// 如果堆栈仍然包含元素,那么它是一个无效的表达式。return stack.isEmpty();}
}
简易版:
简易版:
import java.util.Stack;
// 有效的括号
public class Solution {public boolean isValid(String s){
// 声明一个栈
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++){// 遍历字符串
char c = s.charAt(i); // 转存为 char
if (c == '(' || c == '[' || c == '{'){
// 如果是左括号就 push 进去
stack.push(c);
}else {// 否则检查是否与栈顶元素匹配
if (stack.isEmpty())
return false;
// 将栈顶元素弹出
char topChar = stack.pop();
// 如果并不能匹配返回 false
if (c == ')' && topChar != '(')
return false;
if (c == ']' && topChar != '[')
return false;
if (c == '}' && topChar != '{')
return false;
}
}
// 最后检查栈是否为空
return stack.isEmpty();}
}
结合自己的理解记录了学习的过程
图片来自网络
正文完