Parenthesis Brackets Matching using Stack algorithm

Question

For example if the parenthesis brackets is matching in the following                      and so on but if the parenthesis brackets is not matching it should return false  eg                      and so on  Can you please check this code  Thanks in advance   public static boolean isParenthesisMatch String str        Stack lt Character gt  stack   new Stack lt Character gt          char c      for int i 0  i  lt  str length    i              c   str charAt i            if c                     return false           if c                     stack push c            if c                       stack push c               if c                         if stack empty                        return false                  else if stack peek                               stack pop                      else if c                     if stack empty                    return false              else if stack peek                               stack pop                    else                     return false                    return stack empty       public static void main String   args                String str               System out println Weekly12 parenthesisOtherMatching str

User · Answer

Actually  there is no need to check any cases  manually   You can just run the following algorithm    Iterate over the given sequence  Start with an empty stack  If the current char is an opening bracket  just push it to the stack  If it s a closing bracket  check that the stack is not empty and the top element of the step is an appropriate opening bracket that it is  matches this one   If it is not  report an error  Otherwise  pop the top element from the stack  In the end  the sequence is correct iff the stack is empty    Why is it correct  Here is a sketch of a proof  if this algorithm reported that the sequence is corrected  it had found a matching pair of all brackets  Thus  the sequence is indeed correct by definition  If it has reported an error     If the stack was not empty in the end  the balance of opening and closing brackets is not zero  Thus  it is not a correct sequence  If the stack was empty when we had to pop an element  the balance is off again  If there was a wrong element on top of the stack  a pair of  wrong  brackets should match each other  It means that the sequence is not correct    I have shown that     If the algorithm has reported that the sequence is correct  it is correct  If the algorithm has reported that the sequence is not correct  it is incorrect note that I do not use the fact that there are no other cases except those that are mentioned in your question      This two points imply that this algorithm works for all possible inputs

User · Answer

import java util     class StackDemo        public static void main String   argh            boolean flag   true          String str                       int l   str length            flag   true          Stack lt String gt  st   new Stack lt String gt             for  int i   0  i  lt  l  i                  String test   str substring i  i   1               if  test equals                         st push test                 else if  test equals                         st push test                 else if  test equals                         st push test                 else if  test equals                         if  st empty                          flag   false                      break                                    if  st peek   equals                             st pop                      else                       flag   false                      break                                  else if  test equals                         if  st empty                          flag   false                      break                                    if  st peek   equals                             st pop                      else                       flag   false                      break                                  else if  test equals                         if  st empty                          flag   false                      break                                    if  st peek   equals                             st pop                      else                       flag   false                      break                                                    if  flag  amp  amp  st empty                System out println  true            else             System out println  false

User · Answer

public String checkString String value        Stack lt Character gt  stack   new Stack lt  gt         char topStackChar   0      for  int i   0  i  lt  value length    i              if   stack isEmpty                  topStackChar   stack peek                      stack push value charAt i            if   stack isEmpty    amp  amp  stack size    gt  1                if   topStackChar         amp  amp  stack peek                                   topStackChar         amp  amp  stack peek                                   topStackChar         amp  amp  stack peek                              stack pop                    stack pop                                      return stack isEmpty      YES     NO

User · Answer

Algorithm to use for checking well balanced parenthesis -   Declare a map matchingParenMap and initialize it with closing and opening bracket of each type as the key-value pair respectively  Declare a set openingParenSet and initialize it with the values of matchingParenMap  Declare a stack parenStack which will store the opening brackets           and      Now traverse the string expression input    If the current character is an opening bracket                   then push it to the  parenStack  If the current character is a closing bracket                   then pop from  parenStack and if the popped character is equal to the matching starting bracket in  matchingParenMap then continue looping else return false   After complete traversal if no opening brackets are left in parenStack it means it is a well balanced expression    I have explained the code snippet of the algorithm used on my blog  Check link - http   hetalrachh home blog 2019 12 25 stack-data-structure

User · Answer

This code is easier to understand   public static boolean CheckParentesis String str        if  str isEmpty            return true       Stack lt Character gt  stack   new Stack lt Character gt         for  int i   0  i  lt  str length    i                  char current   str charAt i           if  current           current           current                               stack push current                       if  current           current           current                               if  stack isEmpty                    return false               char last   stack peek                if  current         amp  amp  last           current         amp  amp  last           current         amp  amp  last                         stack pop                else                  return false                        return stack isEmpty

User · Answer

Algorithm is   1 Create a stack  2 while end of input is not reached      i if the character read is not a sysmbol to be balanced  ignore it      ii if the character is       then push it to stack     iii If it is a       then if           a the stack is empty report an error catch it  i e not balanced          b else pop the stack      iv if element popped is not corresponding to opening sysmbol then report error   3  In the end if stack is not empty report error else expression is balanced      In Java code                     public class StackDemo       public static void main String   args  throws Exception           System out println  --Bracket checker--            CharStackArray stack   new CharStackArray 10           stack balanceSymbol   a b c  e-f p-q                 stack display                   class CharStackArray           private char   array          private int top          private int capacity           public CharStackArray int cap                capacity   cap              array   new char capacity               top   -1                     public void push char data                array   top    data                     public char pop                 return array top--                      public void display                 for  int i   0  i  lt   top  i                      System out print array i     - gt                                      public char peek   throws Exception               return array top                        Call this method by passing a string expression           public void balanceSymbol String str                try                   char   arr   str toCharArray                    for  int i   0  i  lt  arr length  i                          if  arr i            arr i            arr i                                  push arr i                        else if  arr i          amp  amp  peek                                   pop                        else if  arr i          amp  amp  peek                                   pop                        else if  arr i          amp  amp  peek                                   pop                                      if  isEmpty                          System out println  String is balanced                      else                       System out println  String is not balanced                                    catch  Exception e                    System out println  String not balanced                                      public boolean isEmpty                 return  top    -1                     Output   --Bracket checker--  String is balanced

User · Answer

Problem Statement  Check for balanced parentheses in an expression Or Match for Open Closing Brackets If you appeared for coding interview round then you might have encountered this problem before  This is a pretty common question and can be solved by using Stack Data Structure Solution in C          public void OpenClosingBracketsMatch                         string pattern    quot             quot               Dictionary lt char  char gt  matchLookup   new Dictionary lt char  char gt                 matchLookup                         matchLookup                         matchLookup                         Stack lt char gt  stck   new Stack lt char gt                 for  int i   0  i  lt  pattern Length  i                                  char currentChar   pattern i                   if  matchLookup ContainsKey currentChar                       stck Push currentChar                   else if  currentChar           currentChar           currentChar                                               char topCharFromStack   stck Peek                        if  matchLookup topCharFromStack     currentChar                                                Console WriteLine  quot NOT Matched quot                            return                                                                     Console WriteLine  quot Matched quot               For more information  you may also refer to this link  https   www geeksforgeeks org check-for-balanced-parentheses-in-an-expression

User · Answer

import java util     public class Parenthesis          public static void main String   okok                 Scanner sc  new Scanner System in           String str sc next            System out println isValid str               public static int isValid String a            if a length   2  0                         return 0                    else if a length    0                         return 1                    else                        char c   a toCharArray                Stack lt Character gt  stk    new Stack lt Character gt                 for int i 0 i lt c length i                                  if c i          c i          c i                                              stk push c i                                      else                                       if stk isEmpty                                                  return 0                            break                                            else                                                char cc c i                           if cc       amp  amp  stk peek                                                                stk pop                                                      else if cc       amp  amp  stk peek                                                                 stk pop                                                      else if cc       amp  amp  stk peek                                                                 stk pop                                                                                                 if stk isEmpty                                  return 1               else                               return 0

User · Answer

import java util Stack   class Demo        char c       public  boolean checkParan String word                Stack lt Character gt  sta   new Stack lt Character gt             for int i 0 i lt word length   i                         c word charAt i               if c                                 sta push c                 System out println    Pushed into the stack                           else if c                                 sta push c                 System out println    Pushed into the stack                          else if c                                 if sta empty                                      System out println  Stack is Empty                      return false                                else if sta peek                                            sta pop                      System out println     is poped from the Stack                                  else if sta peek         amp  amp  sta empty                                      System out println  Stack is Empty                      return false                                        else if c                                 if sta empty                                   System out println  Stack is Empty                  return false                                else if sta peek                                           sta pop                      System out println     is poped from the Stack                                            else if c                                 if sta empty                                     System out println  Stack is empty only   parenthesis in Stack                                                      System out print  The top element is     sta peek         return sta empty                      public class ParaenthesisChehck                    param args the command line arguments             public static void main String   args               TODO code application logic here        Demo d1  new Demo             d1 checkParan                d1 checkParan                 d1 checkParan                 d1 checkParan                  d1 checkParan   123            d1 checkParan

User · Answer

Your code has some confusion in its handling of the     and     characters   It should be entirely parallel to how you handle     and       This code  modified slightly from yours  seems to work properly   public static boolean isParenthesisMatch String str        if  str charAt 0                  return false       Stack lt Character gt  stack   new Stack lt Character gt          char c      for int i 0  i  lt  str length    i              c   str charAt i            if c                     stack push c           else if c                     stack push c           else if c                     if stack empty                    return false              else if stack peek                           stack pop                else                 return false          else if c                     if stack empty                    return false              else if stack peek                           stack pop                else                 return false            return stack empty

User · Answer

here is my solution using c   if brackets are matched then returns true if not then gives false   include  lt iostream gt   include  lt stack gt   include  lt string h gt  using namespace std   int matchbracket string expr       stack lt char gt  st      int i      char x      for i 0 i lt expr length   i             if expr i        expr i        expr i                  st push expr i                       if st empty             return -1          switch expr i                case                    x expr i                st pop                 if x       x                     return 0                break                           case                    x expr i                st pop                 if x       x                     return 0                break                       case                   x expr i               st pop                if x       x                    return 1               break                        return st empty        int main      string expr   cin gt  gt expr     if matchbracket expr   1    cout lt  lt  quot  nTRUE n quot     else   cout lt  lt  quot  nFALSE n quot

User · Answer

Here s a solution in Python      usr bin env python  def brackets match brackets       stack          for char in brackets          if char        or char        or char                     stack append char          if char                     if stack -1                          stack pop               else                  return False         elif char                     if stack -1                          stack pop               else                  return False         elif char                     if stack -1                          stack pop               else                  return False     if len stack     0          return True     else          return False  if   name         main         print brackets match  This is testing        if brackets have match

User · Answer

public static bool IsBalanced string input                Dictionary lt char  char gt  bracketPairs   new Dictionary lt char  char gt                                                                                    lt      gt                     Stack lt char gt  brackets   new Stack lt char gt              try                          Iterate through each character in the input string             foreach  char c in input                                   check if the character is one of the  opening  brackets                 if  bracketPairs Keys Contains c                                            if yes  push to stack                     brackets Push c                                     else                        check if the character is one of the  closing  brackets                     if  bracketPairs Values Contains c                                                    check if the closing bracket matches the  latest   opening  bracket                         if  c    bracketPairs brackets First                                                           brackets Pop                                                      else                                if not  its an unbalanced string                             return false                                            else                            continue looking                         continue                                  catch                          an exception will be caught in case a closing bracket is found                  before any opening bracket                 that implies  the string is not balanced  Return false             return false                        Ensure all brackets are closed         return brackets Count      0   true   false

User · Answer

basic code non strack algorithm just started learning java ignore space and time                          -a - gt      -b - gt  replace a     - gt  reverse a      - gt     Split string to substring         next     next     next    public class testbrackets       static String stringfirst      static String stringsecond      static int open   0      public static void main String   args            splitstring                    static void splitstring String str        int len   str length        for int i 0 i lt  len-1 i             stringfirst             stringsecond             System out println  loop starttttttt            char a   str charAt i       if a       a       a                     open   open 1          continue            if a       a       a                if open  0               System out println open  started with closing brace                return                    String stringfirst str substring i-open  i           System out println  stringfirst  stringfirst           String stringsecond str substring i  i open           System out println  stringsecond  stringsecond           replace stringfirst  stringsecond                  i  i open -1      open 0      System out println i                   static void replace String stringfirst  String stringsecond           stringfirst   stringfirst replace                    stringfirst   stringfirst replace                    stringfirst   stringfirst replace                    StringBuilder stringfirst1   new StringBuilder stringfirst           stringfirst   stringfirst1 reverse   toString        System out println  stringfirst  stringfirst       System out println  stringsecond  stringsecond   if stringfirst equals stringsecond        System out println  pass          else          System out println  fail            System exit 0

User · Answer

Check balanced parenthesis or brackets with stack--    var excp           a b b     c d              var stk             function bracket balance          for var i 0 i lt excp length i               if excp i          excp i          excp i                      stk push excp i               else if excp i         amp  amp  stk pop                         return false             else if excp i         amp  amp  stk pop                         return false             else if excp i         amp  amp  stk pop                         return false                             return true          console log bracket balance         Parenthesis are balance then return true else false

User · Answer

in java you don t want to compare the string or char by    signs  you would use equals method  equalsIgnoreCase or something of the like  if you use    it must point to the same memory location  In the method below I attempted to use ints to get around this  using ints here from the string index since every opening brace has a closing brace  I wanted to use location match instead of a comparison match  But i think with this you have to be intentional in where you place the characters of the string  Lets also consider that Yes   true and No   false for simplicity  This answer assumes that you passed an array of strings to inspect and required an array of if yes  they matched  or No  they didn t   import java util Stack        public static void main String   args           String   arrayOfBraces   new String                                                           Example       is balanced        Example        is not balanced         Examples           is balanced                  is balanced                 is  not  balanced      String   arrayOfBraces    new String                                                                               String   answers          new String arrayOfBraces length            String openers                       String closers                       String stringToInspect             Stack lt String gt  stack       new Stack lt String gt           for  int i   0  i  lt  arrayOfBraces length  i               stringToInspect   arrayOfBraces i           for  int j   0  j  lt  stringToInspect length    j                              if stack isEmpty                     if  openers indexOf stringToInspect charAt j   gt  0                        stack push    stringToInspect charAt j                                         else                      answers i    NO                       j stringToInspect length                                                                   else if openers indexOf stringToInspect charAt j   gt  0                   stack push    stringToInspect charAt j                                 else                  String comparator   stack pop                    int compLoc   openers indexOf comparator                   int thisLoc   closers indexOf stringToInspect charAt j                     if  compLoc    thisLoc                        answers i    NO                       j stringToInspect length                                                           else                      if stack empty    amp  amp   j   stringToInspect length  -1                            answers i    YES                                                                              System out println answers length                for  int j   0  j  lt  answers length  j              System out println answers j

User · Answer

public static boolean isBalanced String s        Map lt Character  Character gt  openClosePair   new HashMap lt Character  Character gt         openClosePair put                openClosePair put                openClosePair put                  Stack lt Character gt  stack   new Stack lt Character gt         for  int i   0  i  lt  s length    i               if  openClosePair containsKey s charAt i                  stack push s charAt i               else if   openClosePair containsValue s charAt i                  if  stack isEmpty                    return false              if  openClosePair get stack pop       s charAt i                   return false                        ignore all other characters            return stack isEmpty

User · Answer

I have seen answers here and almost all did well  However  I have written my own version that utilizes a Dictionary for managing the bracket pairs and a stack to monitor the order of detected braces  I have also written a blog post for this   Here is my class  public class FormulaValidator          Question  Check if a string is balanced  Every opening bracket is matched by a closing bracket in a correct position                             Example       is balanced        Example        is not balanced         Examples           is balanced                  is balanced                      is  not  balanced         Input  string  containing the bracket symbols only        Output  true or false     public bool IsBalanced string input                var brackets   BuildBracketMap            var openingBraces   new Stack lt char gt             var inputCharacters   input ToCharArray             foreach  char character in inputCharacters                        if  brackets ContainsKey character                                 openingBraces Push character                              if  brackets ContainsValue character                                 var closingBracket   character                  var openingBracket   brackets FirstOrDefault x   gt  x Value    closingBracket  Key                   if  openingBraces Peek      openingBracket                      openingBraces Pop                    else                     return false                                   return openingBraces Count    0             private Dictionary lt char  char gt  BuildBracketMap                 return new Dictionary lt char  char gt

User · Answer

import java util     public class MatchBrackets        public static void main String   argh            String input                       System out println   input            char    openChars                           char    closeChars                           Stack lt Character gt  stack   new Stack lt Character gt              for  int i   0  i  lt  input length    i                   String x       input charAt i                if  String valueOf openChars  indexOf x     -1                                stack push input charAt i                              else                               Character lastOpener   stack peek                    int idx1   String valueOf openChars  indexOf lastOpener toString                     int idx2   String valueOf closeChars  indexOf x                    if  idx1    idx2                                        System out println  false                        return                                    else                                       stack pop                                                       if  stack size      0              System out println  true            else             System out println  false

User · Answer

public static boolean isValidExpression String expression        Map lt Character  Character gt  openClosePair   new HashMap lt Character  Character gt         openClosePair put                openClosePair put                openClosePair put                        Stack lt Character gt  stack   new Stack lt Character gt         for char ch   expression toCharArray              if openClosePair containsKey ch                 if stack pop      openClosePair get ch                     return false                          else if openClosePair values   contains ch                 stack push ch                        return stack isEmpty

User · Answer

You re doing some extra checks that aren t needed  Doesn t make any diff to functionality  but a cleaner way to write your code would be   public static boolean isParenthesisMatch String str        Stack lt Character gt  stack   new Stack lt Character gt         char c       for  int i   0  i  lt  str length    i              c   str charAt i           if  c           c                     stack push c           else if  stack empty                return false          else if  c                       if  stack pop                           return false            else if  c                       if  stack pop                           return false                      return stack empty        There is no reason to peek at a paranthesis before removing it from the stack  I d also consider wrapping instruction blocks in parantheses to improve readability

User · Answer

If you want to have a look at my code  Just for reference   public class Default        public static void main String   args  throws IOException            BufferedReader br   new BufferedReader new InputStreamReader System in            int numOfString   Integer parseInt br readLine             String s          String stringBalanced    YES           Stack lt Character gt  exprStack   new Stack lt Character gt              while   s   br readLine       null                stringBalanced    YES               int length   s length   - 1              for  int i   0  i  lt   length  i                      char tmp   s charAt i                    if tmp         tmp         tmp                            exprStack push tmp                    else if tmp         tmp         tmp                            if  exprStack isEmpty                             char peekElement   exprStack peek                            exprStack pop                            if tmp       amp  amp  peekElement                                    stringBalanced  NO                            else if tmp       amp  amp  peekElement                                    stringBalanced  NO                            else if tmp       amp  amp  peekElement                                    stringBalanced  NO                                                  else                          stringBalanced  NO                           break                                                                      if  exprStack isEmpty                     stringBalanced    NO                              exprStack clear                System out println stringBalanced

User · Answer

I think is the best answer   public boolean isValid String s        Map lt Character  Character gt  map   new HashMap lt  gt         map put                map put                map put                Stack lt Character gt  stack   new Stack lt  gt         for char c   s toCharArray             if map containsKey c                stack push c             else if  stack empty    amp  amp  map get stack peek     c               stack pop              else               return false                      return stack empty

User · Answer

Brackets Matching program without using stack    Here i used string for replacement of stack implementations like push and pop operations    package java prac      import java util        public class BracketsChecker        public static void main String   args            System out println  - - - Brackets Checker   without stack   - - - n n            Scanner scan new Scanner System in           System out print  Input                String s   scan nextLine            scan close            System out println   n   working    n            String o                String c                String x              int check  0          for  int i   0  i  lt  s length    i                  if o contains String valueOf s charAt i                      x  s charAt i                           System out println  In     x      stack in              else if c contains String valueOf s charAt i                        char temp   s charAt i                   if temp       temp                        if temp       temp                        if temp       temp                        if x charAt x length  -1   temp                        x     x substring 1 x length  -1                         System out println  Out     x        stack out              else               check 1                                                   if x length    1  amp  amp  check  0                 System out println   n nCompilation Success  n n   github com sharanstark 2k19             else               System out println   n nCompilation Error  n n   github com sharanstark 2k19

User · Answer

I tried this using javascript below is the result    function bracesChecker str      if  str        return true        var openingBraces                      var closingBraces                      var stack         var openIndex    var closeIndex      check for opening Braces in the val   for  var i   0  len   str length  i  lt  len  i          openIndex   openingBraces indexOf str i        closeIndex   closingBraces indexOf str i        if openIndex     -1          stack push str i                if closeIndex     -1          if openingBraces closeIndex      stack stack length-1              stack pop            else           return false                      if stack length     0        return true      else       return false        var testStrings               test                                 test  test           test  test          test  yo  test          test  test          te  s  t  test         te  s  t  test      testStrings forEach val   gt  console log    val    gt    bracesChecker val

User · Answer

Optimized implementation using Stacks and Switch statement   public class JavaStack    public static void main String   args        Scanner sc   new Scanner System in          Stack lt Character gt  s   new Stack lt Character gt          while  sc hasNext              String input   sc next             for  int i   0  i  lt  input length    i                  char c   input charAt i               switch  c                     case                          s push c   break                  case                          s push c   break                  case                          s push c   break                  case                          if   s isEmpty    amp  amp  s peek   equals                                 s pop                          else                           s push c                         break                  case                          if   s isEmpty    amp  amp  s peek   equals                                 s pop                          else                           s push c                         break                  case                          if   s isEmpty    amp  amp  s peek   equals                                 s pop                          else                           s push c                         break                   default                      s push  x    break                                    if  s empty                  System out println  true              else               System out println  false                s clear                          Cheers

User · Answer

The algorithm    scan the string pushing to a stack for every     found in the string  if char     scanned  pop one     from the stack   Now  parentheses are balanced for two conditions        can be popped from the stack for every     found in the string  and stack is empty at the end  when the entire string is processed

User · Answer

package com balance braces   import java util Arrays  import java util Stack   public class BalanceBraces    public static void main String   args         String   values                           String   rsult   match values        Arrays stream rsult  forEach str - gt  System out println str       static String   match String   values         String   returnString   new String values length        for  int i   0  i  lt  values length  i              String value   values i            if  value length     2    0                returnString i     NO               continue            else                Stack lt Character gt  buffer   new Stack lt Character gt                 for  char ch   value toCharArray                       if  buffer isEmpty                          buffer add ch                     else                       if  isMatchedBrace buffer peek    ch                             buffer pop                          else                           buffer push ch                                                           if  buffer isEmpty                          returnString i     YES                     else                       returnString i     FALSE                                                         return returnString     static boolean isMatchedBrace char start  char endmatch        if  start                 return endmatch             if  start                 return endmatch             if  start                 return endmatch             return false

User · Answer

Was asked to implement this algorithm at live coding interview  here s my refactored solution in C    Git Tests

User · Answer

Ganesan s answer above is not correct and StackOverflow is not letting me comment or Edit his post  So below is the correct answer  Ganesan has an incorrect facing     and is missing the stack isEmpty   check    The below code will return true if the braces are properly matching   public static boolean isValidExpression String expression        Map lt Character  Character gt  openClosePair   new HashMap lt Character  Character gt         openClosePair put                openClosePair put                openClosePair put                 Stack lt Character gt  stack   new Stack lt Character gt         for char ch   expression toCharArray              if openClosePair containsKey ch                 if stack isEmpty      stack pop      openClosePair get ch                     return false                          else if openClosePair values   contains ch                 stack push ch                        return stack isEmpty

[java] Parenthesis/Brackets Matching using Stack algorithm

Examples related to java

Examples related to stack

Examples related to parentheses