Using the stack algorithm for parenthesis matching

Question

I have used Stacks to check for brackets mismatch. (Parentheses matching problem using Stack algorithm)

Any suggestions on how to improve the code?

I have tried various examples and it works without error but I feel there is a lack of specificity. How do I work on that?

Side note: I think there's a stack reference type in Java but I am not allowed to use that.

import java.util.Scanner; 
class ParensMatching
{
    static  Character Stack[]= new Character[25]; 
    static int ptr = -1;

    static void push(char ch)
    {
        if(ptr+1 < 25)
        {
            Stack[++ptr]= ch; 
        }
        else 
        {
            System.out.println("Overflow!! ");
        }

    }

    static int pop()
    {

        if (ptr == -1)
        {
            System.out.println("Underflow!!");
            return 999; 
        }
        int value = Stack[ptr]; 
        ptr = ptr-1; 
        return value; 
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while(true)
        {
            System.out.println("Enter a string");
            String str = sc.nextLine(); 
            char temp; 
            int i = 0; 
            outer: 
            for (i = 0; i< str.length(); i++)
            {
                if(str.charAt(i)== '('|| str.charAt(i)== '{' || str.charAt(i)== '[')
                {
                    push(str.charAt(i));
                    temp = str.charAt(i); 
                }
                else if(str.charAt(i)== ')')
                {
                    if(pop()!= '(')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer; 
                    }
                }
                else if(str.charAt(i)== '}')
                {
                    if(pop()!= '{')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer; 
                    }
                }
                else if(str.charAt(i)== ']')
                {
                    if(pop()!= '[')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer; 
                    }
                }
            }
            if(ptr != -1)
            {
                System.out.println("Missing closing parens!!");
            }
            else if (i == str.length())
            {
                System.out.println("Success. No unmatched parens");
            }
            System.out.println("Enter 2 to stop testing");
            int n = sc.nextInt(); 
            if(n == 2)
                break; 
            else
                continue; 
        }

    }
}

Answer 1

Make a separate stack class. Even if this is a one time thing it is good OO practice.

Good encapsulation will not allow the main program to access the stack's internal structure, ptr for example. Methods like Stack.isEmpty() would be more user-friendly.

If popping "below the bottom" of the stack, it's better returning null rather than a specific out of range ptr value. I think the stack should be self-expanding, but if intentional design says it is fixed length then fine.

Design classes with excellent customer service built in.

---

if (ptr == -1)

I suggest ptr <= -1. This is really the condition and it is more error tolerant. What if some other bug decremented to -2 before this check?

---

Data structures to simplify code

We want to avoid this:

if(str.charAt(i)== '('|| str.charAt(i)== '{' || str.charAt(i)== '[')

Not extensible, error prone, hard to read. The goal is something like this:

if( OpenDelimiters.contains ( str.charAt(i) ) )

There might be OpenDelimiters, CloseDelimiters, PairDelimiter structures - that might seem like a lot, but code gets real simple real fast as seen above. Adding delimiters means no code changes, just add to the data structures.

---

Edit - RE: if(ptr == -1)

This needs clarification. Please be patient, this is a case of something simple taking extensive explanation to show how and why it is wrong.

The big picture is this:

• code the algorithm as precisely as possible
• Don't assume simple code is bug free
• Even correct arithmetic, at the bits and bytes level can be surprisingly inaccurate.
• Make code robust because ongoing maintenance is toxic to code.
• Develop good coding techniques that reduce bug risk and apply them consistently

---

Algorithm vis-a-vis Code

Pretend the program calculated ptr = -2 instead of -1. Then if(ptr == -1) does not catch it. What is the error, the arithmetic or the condition or both? Change the condition to if(ptr == -2) and the program is fixed, right? How about we just throw an exception, is the program fixed now? If it runs why not?

• When pop()ing we need to catch "going off the bottom" of the stack. By definition that means an index less than zero. That algorithm definition is accurately coded as ptr < 0.
  • Given the above, if ptr is -2 - this is not a program error per se. The program will keep running correctly. The pop algorithm handles that condition - index is less than zero.
  • if ptr is -2 - now this must be coding error because we intended -1. Lucky we're testing for < 0. Fix the arithmetic bug even if the conditional statement tolerates it. The arithmetic error and the conditional logic are two separate things. Arithmetic errors should be caught in testing. P.S.: throwing exceptions for arithmetic errors is just wrong!!
  • if(ptr == -1) is not an execution bug but it is wrong. The algorithm is not coded correctly. There is no arithmetic error yet code change has more potential for inducing execution bugs. The program will fail if the value is anything except -1.

---

Bit-level numbers

Testing for exact values can bite you. It just became easier for me to quit testing for exactly -1 than to try to out smart the compiler or interpreter or my inadvertent bugs-waiting-to-happen or the idiot maintenance programmer (sometimes that was me).

Binary numbers in memory have inherent problems just like base-10 does. 1/3 in base-10 is .333... to infinity. Sometimes numbers converted to binary are like that.

Sometimes computation induces errors. For example, the sum of a Taylor series added "forward" can - will - be different from adding "backwards". I.E. 1/2 + 1/3 + 1/4 + 1/5 ...... Do this for many thousand of terms and you'll see.

Even integer arithmetic can be quirky in some languages. JavaScript, for example, does not have integers. All numbers are stored as floating point in memory. Google "javascript the weird parts" and you'll see funky numeric WTFs.

end Edit

Answer 2

Java naming conventions

Please follow the Java naming conventions. Variables should start with a lowercase character, so it should read (also note the placing of [] makes it clearer that stack is an array of Character)

static  Character[] stack= new Character[25]; 

Why maximum stack size?

There is no given requirement for the limit of the size of the stack, so you should not use a fixed-size data structure like array, but rather opt for something like List

 static  List<Character> stack= new ArrayList<>(); 

Separation of concerns

There are two functionalities in you code directly interwoven. First, there is the 'Stack', then there is the usage of the Stack. Move all the Stack related functionality to its own class.

Don't use magic values

If there is an error in the state of the stack (for example, if you try to pop() an empty stack, you could throw an Exception, for example a NoSuchElementException. Or you can have the Stack use Optional and return Optional.empty(). Or even return null if no empty values on the stack are allowed.

See for example the question here. Also check the answers.

Pair the parentheses, separate to own data type

You could implement a Delimiter enum type, like such:

enum Delimiter
{
  PARENTHESES( '(', ')' ),
  BRACES     ( '{', '}' ),
  BRACKETS   ( '[', ']' );
  //easily expandable with for example: 〔 〕 – tortoise shell brackets
  

  public final char openChar;
  public final char closeChar;

  public Delimiter(char openChar, char closeChar)
  {
      this.openChar = openChar;
      this.closeChar = closeChar;
  }
}

Then, when looping over the characters, you could use:

 for (i = 0; i< str.length(); i++)
 {
     char c = str.charAt(i);
     for (Delimiter delimiter : Delimiter.values())
     {
          if (c == delimiter.openChar)
          {
              stack.push(delimiter);
          } 
          else if (c == delimiter.closeChar)
          {
              //pop the stack and check if the closechar matches the openchar of the popped element

          }
     }