【Java版oj】day07括号匹配

朱雀 2024-03-31 17:29 29阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [合法括号序列判断\_牛客题霸\_牛客网][Link 1]
> 
> ### 描述 ###
> 
> 给定一个字符串**A**和其长度**n**，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。
> 
> 测试样例：
> 
> "(()())",6  
> 返回：true
> 
> 测试样例：
> 
> "()a()()",7
> 
> 返回：false
> 
> 测试样例：
> 
> "()(()()",7
> 
> 返回：false

> ## 二、问题分析 ##
> 
> 本题用栈结构实现，栈中存放左括号，当遇到右括号之后，检查栈中是否有左括号，如果有则出栈，如果没有，则说明不匹配。

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     public class Parenthesis {
>         public boolean chkParenthesis(String A, int n) {
>             // write code here
>             Stack <Character> stack = new Stack<>();
>             for (int i = 0; i < A.length(); i++) {
>                 if (A.charAt(i) != '(' && A.charAt(i) != ')') {
>                     return false;
>                 }
>             }
>             for (int j = 0; j < A.length(); j++) {
>                 if (A.charAt(j) == '(') {
>                     stack.push(A.charAt(j));
>                     continue;
>                 }
>                 if (A.charAt(j) == ')') {
>                     if (stack.peek() == null) {
>                         return false;
>                     } else {
>                         stack.pop();
>                     }
>                     continue;
>                 }
>             }
>             return true;
>         }
>     }
> 
> ![0fdf2a90a56a4fd29bb793e717bffe2e.png][]

--------------------

![b641d23cc356426abb8665646bd3c44f.png][]

[Link 1]: https://www.nowcoder.com/practice/d8acfa0619814b2d98f12c071aef20d4?tpId=8&&tqId=11039&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[0fdf2a90a56a4fd29bb793e717bffe2e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6361d03ee2d043d98e6da9f55f51db50.png
[b641d23cc356426abb8665646bd3c44f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/08be40e3db434c92bc07e937c56448a2.png