利用栈和HashMap处理括号匹配问题

如何处理相机设置与环境光线不匹配的问题 #生活技巧# #数码产品使用技巧# #相机设置调整教学#

问题：

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

算法：

1、初始化栈
2、依次处理表达式的每个符号
3、如果遇到右括号，检查栈顶元素：如果栈顶元素是一个相同类型的左括号，将栈顶元素取出，否则，意味着表达式无效；
4、如果遇到左括号，将其推到栈上
5、所有符号处理结束之后，若栈中仍有元素，意味着表达式无效

对应的代码：
1、

Stack<Character> stack = new Stack<Character>(); 1

2、

for( int i = 0; i < s.length(); i++) //(String s)是待处理的表达式字符串char c = s.charAt(i); 12

3、

if(this.mappings.containsKey(c)) ｛if(stack.isEmpty() || stack.peek() != this.mappings.get(c)); //键值对——通过key得到value的值return false;elsestack.pop(); ｝ 1234567

另一种更高效的做法： 如果表达式有效，那么在遇到右括号时栈顶元素必须是对应的左括号；否则表达式无效。因此，栈顶元素非取即无效。所以，可以直接将栈顶元素先取出来, 若取出的栈顶元素与右括号不匹配，再返回false即可。

char topElement = stack.empty()? '#' : stack.pop(); if (topElement != this.mappings.get(c))return false; 123

4、

else stack.push(c); 1

5、

return stack.isEmpty 1

另：先在构造函数中初始化HashMap

private HashMap<Character, Character> mappings; // Initialize hash map with mappings. This simply makes the code easier to read. public Solution() { this.mappings = new HashMap<Character, Character>(); this.mappings.put(')', '('); this.mappings.put('}', '{'); this.mappings.put(']', '['); } 123456789

笔记:

Stack的API

boolean empty()
E peek()
E pop()
E push(E object)
int search(Object o)

HashMap的API

void clear()
Object clone()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set<Entry<K, V>> entrySet()
V get(Object key)
boolean isEmpty()
Set keySet()
V put(K key, V value)
void putAll(Map<? extends K, ? extends V> map)
V remove(Object key)
int size()
Collection values()

网址：利用栈和HashMap处理括号匹配问题 https://www.yuejiaxmz.com/news/view/786672

相关内容

栈和队列
请问所有房间都配备空调和卫生间？#大理洱海简海慢生活主题客栈#请 爱问知识人
数据结构：栈的实现及应用场景
内存管理与优化技巧：栈、堆和静态内存
当利用大小为n的数组顺序存储一个栈时,假定用top=n表示栈空,则每次向这个栈插
数据结构详解：从基础到高级应用实例
队列原理与应用实例
智能匹配心理咨询师服务平台
经典String str = new String(“abc”);内存分配问题
如何解决灶台的布局问题？这类问题怎样合理处理？

随便看看