时间:2021-05-19
如何使用栈来判定括号是否匹配
对于给定的表达式,可以使用栈来实现括号匹配判定,这个算法在编译器中非常重要,解析器每次读入
一个字符,如果字符是一个开分隔符,如(,【,{,入栈,若读入的是闭分隔符),】,},出栈,如果两者匹配,继续解析字符串,如果不匹配,解析器错误
算法思路
1.创建一个栈
2.当(当前字符不等于输入的结束字符)
(1)如果当前字符不是匹配的字符,判断栈内是否为空,如果栈为空,括号必然不完整
(2)如果字符是一个开分隔符,那么将其入栈
(3)如果字符是一个闭分隔符,,且栈不为空,则判断是否匹配
(4)栈结束后判断是否为空,不为空则括号匹配错误
代码示例
class Solution { public boolean isValid(String s) { //声明匹配词典 Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); //创建栈 Stack<Character> stack = new Stack<>(); for (char ch : s.toCharArray()) { //开分隔符入栈 if (ch == '(' || ch == '[' || ch == '{') { stack.push(ch); } //出栈并且栈非空进行匹配 else if (stack.isEmpty() || stack.pop() != map.get(ch)){ return false; } } //如果栈非空则括号匹配错误 return stack.isEmpty(); }}1.括号匹配算法
//括号匹配算法 public void pipei()throws Exception{ char temp,ch; int match; //记录匹配结果 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ch=(char) br.read(); //输入一个字符 while(ch!='0'){ if(getTop()==-1){ push(ch); }else{ temp=pop(); //取出栈顶元素 match=0; //判断是否匹配(默认不匹配) if(temp=='('&&ch==')') match=1; if(temp=='['&&ch==']') match=1; if(temp=='{'&&ch=='}') match=1; if(temp=='<'&&ch=='>') match=1; if(match==0){ //如果不匹配 push(temp); //将原栈顶元素重新入栈 push(ch); //将输入的括号字符入栈 } } ch=(char) br.read(); //输入下一个字符 } if(isEmpty()){ System.out.println("输入的括号完全匹配!"); }else{ System.out.println("输入的括号不匹配,请检查!"); } }2.括号匹配求解示例
package com.cn.datastruct;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Scanner;public class KuoHaoPiPei { static class Stack{ char[] data; //存放数据 int MaxSize; //最大容量 int top; //栈顶指针 //构造方法 public Stack(int MaxSize){ this.MaxSize=MaxSize; data = new char[MaxSize]; top = -1; } public int getMaxSize() { return MaxSize; } public int getTop() { return top; } public boolean isEmpty(){ return top==-1; } public boolean isFull(){ return top+1==MaxSize; } //入栈 public boolean push(char data){ if(isFull()){ System.out.println("栈已满!"); return false; } this.data[++top]=data; return true; } //出栈 public char pop() throws Exception{ if(isEmpty()){ throw new Exception("栈已空!"); } return this.data[top--]; } //获得栈顶元素 public char peek(){ return this.data[getTop()]; } //括号匹配算法 public void pipei()throws Exception{ char temp,ch; int match; //记录匹配结果 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ch=(char) br.read(); //输入一个字符 while(ch!='0'){ if(getTop()==-1){ push(ch); }else{ temp=pop(); //取出栈顶元素 match=0; //判断是否匹配(默认不匹配) if(temp=='('&&ch==')') match=1; if(temp=='['&&ch==']') match=1; if(temp=='{'&&ch=='}') match=1; if(temp=='<'&&ch=='>') match=1; if(match==0){ //如果不匹配 push(temp); //将原栈顶元素重新入栈 push(ch); //将输入的括号字符入栈 } } ch=(char) br.read(); //输入下一个字符 } if(isEmpty()){ System.out.println("输入的括号完全匹配!"); }else{ System.out.println("输入的括号不匹配,请检查!"); } } } public static void main(String[] args) throws Exception { String go; Scanner input = new Scanner(System.in); Stack stack = new Stack(20); System.out.println("括号匹配问题!"); do{ System.out.println("请输入一组括号的组合,以0表示结束。支持的括号包括:{},(),[],<>。"); stack.pipei(); //匹配算法 System.out.print("\n继续匹配吗(y/n)?"); go=input.next(); }while(go.equalsIgnoreCase("y")); System.out.println("匹配结束!"); }}程序运行结果如下:
括号匹配问题!
请输入一组括号的组合,以0表示结束。支持的括号包括:{},(),[],<>。
({[]})<>0
输入的括号完全匹配!
继续匹配吗(y/n)?y
请输入一组括号的组合,以0表示结束。支持的括号包括:{},(),[],<>。
({])0
输入的括号不匹配,请检查!
继续匹配吗(y/n)?n
匹配结束!
到此这篇关于java括号匹配算法求解(用栈实现)的文章就介绍到这了,更多相关java括号匹配算法内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C++自定义栈实现迷宫求解一:迷宫求解是一个锻炼我们的算法求解能力的问题,它的实现方法有很多;今天我们就介绍其中的用栈求解的方法。二:什么是栈:大家应该都有往袋
本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考,具体如下:1、LeetCode官网美网:https://leetcode.com/中文网:h
本文实例讲述了基于PHP实现栈数据结构和括号匹配算法。分享给大家供大家参考,具体如下:栈,体现的是后进先出,即LIFO。队列,体现的是先进先出,即FIFO。栈操
本文实例讲述了Python实现求解括号匹配问题的方法。分享给大家供大家参考,具体如下:这个在本科学习数据结构的时候已经接触很多了,主流的思想是借助栈的压入、弹出
本文实例主要实现:输入一个括号字符串,依次检验,若为左括号则入栈,若为右括号则出栈一个字符判断是否与之相对应,在最后还需判断栈是否为空,如果不为空则不匹配。首先