DSA 16: Stacks - Linter [Part 2]

Recording first attempt writing a (Braces) Linter class
data structures
algorithms
Author

Tony Phung

Published

January 29, 2025

1. Create Linter Class

By incoporating previously created stack class.

1.1 Objectives

  • Syntax Error 1: Open-brace without a close-brace
  • Syntax Error 2: Close-brace without an open-brace
  • Syntax Error 3: Open-brace with incorrect close-brace

1.2 Solution: Psuedo-Code

  • set valid-op-braces: [({
  • set valid-cl-braces: ])}

for char in string:

  • [in-loop] if valid-op-brace:
    • add(), continue
  • [in-loop] if valid-cl-brace:
    • if cl-brace ])} == [({ valid-op-br: pop(), continue
    • if cl-brace ])} == [({ invalid-op-br: Syntax Error 3
    • if stack is empty: Syntax Error 2
  • [out-loop] if stack is not empty: Syntax Error 1

Edit: This psuedo-code was a bit off from what I ended up writing up…

2. Solution

First attempt!

2.1 TonyStack(): Updated

Updated TonyStack() as required to help build and the main class Linter (from 2.2)

class TonyStack():
    def __init__(self):
        print(f"empty stack created")
        self.data = []
        
    def add(self, value):
        self.data.append(value)
        # print(f"{value} ({type(value)}) added. {self.data}")
        print(f"\t'{value}' added. {self.data}")

    def pop(self):
        if len(self.data)>0:
            popped = self.data.pop() # pop() is an in-built obj-method of python's list
            # print(f"{popped} ({type(popped)}) removed. {self.data}")
            print(f"\t'{popped}' removed. {self.data}\n")
        else:
            print(f"\tstack is empty. {self.data}\n")
        
    def read(self):
        if len(self.data)>0:
            last = self.data[-1]
            # print(f"{last} ({type(last)} is at top of stack. {self.data}")
            # print(f"\t'{last}' is at top of stack. {self.data}")
            return last
        else:
            print(f"\tstack is empty. {self.data}\n")

    def clear(self):
        print("...clearing stack...")
        self.__init__()
        # self.data = []

2.2 LinterCls: Commentary

I built this raw (without looking at any solutions). In a future post, I’ll attempt to update it from feedback (from AI, I dont have anyone else to get feedback from at the moment.)

I noticed my use python dictionaries (i.e. hash tables) instead. of if-else due to learning and being more comfortable in implementing them from this chapter.

Prior to this chapter, I would have definitely used a bunch of if-else statements

2.3 LinterCls: Python

class LinterCls():
    valid_open_brace_only_dct = {'(':True, '{':True, '[':True}
    # valid_cl_brace_dct = {')':True, '}':True, ']':True}
    valid_op_cl_dct = {
        ')':'(',
        '}':'{',
        ']':'['
        }
    def __init__(self):
        print(f"linter created")
        self.stack = TonyStack()
    def lint(self, str_list: str):
        
        self.stack.clear() # since we are linting something, the assumption is something afresh with 
        # the fresh input, so remove existing string (issues discovered when runnin tests)
        
        for char in str_list:
            print(f"current char: '{char}'")
            # if char in LinterCls.valid_op_brace_dct: 
            if char in LinterCls.valid_open_brace_only_dct: 
                self.stack.add(char)# no syntax error - close okay
                print("\tmove to next character\n")
                continue
            if char in LinterCls.valid_op_cl_dct and len(self.stack.data)==0: 
                    raise SyntaxError("Syntax Error 2: Closing Brace without Opening Brace")
            elif char in LinterCls.valid_op_cl_dct and len(self.stack.data)>0: # if char is [VALID_CLOSING_BRACE]
                top_of_stack = self.stack.read() # top of stack: we look for matching open brace
                # print(f"\t valid closing brace: check for matchin opening-brace at top-of-stack...")
                # LinterCls.valid_op_cl_dct[char] use key[close_brace] return value[open_brace] from [valid_dict]
                if LinterCls.valid_op_cl_dct[char] == top_of_stack:
                    # print(f"\t{LinterCls.valid_op_cl_dct[char]} vs {top_of_stack}")
                    print(f"\t[CORRECT] opening-brace at top-of-stack: {top_of_stack}")
                    self.stack.pop()
                    continue
                elif LinterCls.valid_op_cl_dct[char] != top_of_stack:
                    print(f"\t[INCORRECT] opening-brace at top-of-stack is Incorrect: {top_of_stack}")
                    # print(f"\t{LinterCls.valid_op_cl_dct[char]} vs {top_of_stack}")
                    raise SyntaxError("Syntax Error 3: Incorrect Closing Brace")
            else:
                print("not a brace: skip!\n")
                # continue
        if len(self.stack.data)>0:
            print(f"end of string: current stack{self.stack.data}")
            raise SyntaxError("Syntax Error 1: Opening Brace Without Closing Brace")
        print("SYNTAX OK!")
tony_linter = LinterCls()
listify = lambda input_string: [char for char in input_string]
linter created
empty stack created

3. Testing

3.1. '{': expected error 1

input_1 = "{"
input_str_list = listify(input_1)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '{'
    '{' added. ['{']
    move to next character

end of string: current stack['{']
Traceback (most recent call last):

  File ~/.local/share/virtualenvs/blog-T-2huGx2/lib/python3.10/site-packages/IPython/core/interactiveshell.py:3577 in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)

  Cell In[6], line 3
    tony_linter.lint(input_str_list)

  Cell In[4], line 44 in lint
    raise SyntaxError("Syntax Error 1: Opening Brace Without Closing Brace")

  File <string>
SyntaxError: Syntax Error 1: Opening Brace Without Closing Brace

3.2 '}': expected error - 2

input_2 = "}"
input_str_list = listify(input_2)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '}'
Traceback (most recent call last):

  File ~/.local/share/virtualenvs/blog-T-2huGx2/lib/python3.10/site-packages/IPython/core/interactiveshell.py:3577 in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)

  Cell In[8], line 3
    tony_linter.lint(input_str_list)

  Cell In[4], line 25 in lint
    raise SyntaxError("Syntax Error 2: Closing Brace without Opening Brace")

  File <string>
SyntaxError: Syntax Error 2: Closing Brace without Opening Brace

3.3 '{)': expected error - 3

input_3 = "{)" 
input_str_list = listify(input_3)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '{'
    '{' added. ['{']
    move to next character

current char: ')'
    [INCORRECT] opening-brace at top-of-stack is Incorrect: {
Traceback (most recent call last):

  File ~/.local/share/virtualenvs/blog-T-2huGx2/lib/python3.10/site-packages/IPython/core/interactiveshell.py:3577 in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)

  Cell In[14], line 3
    tony_linter.lint(input_str_list)

  Cell In[4], line 38 in lint
    raise SyntaxError("Syntax Error 3: Incorrect Closing Brace")

  File <string>
SyntaxError: Syntax Error 3: Incorrect Closing Brace

3.4. '()': expected okay

input_4 = "()"
input_str_list = listify(input_4)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '('
    '(' added. ['(']
    move to next character

current char: ')'
    [CORRECT] opening-brace at top-of-stack: (
    '(' removed. []

SYNTAX OK!

3.5. '[{}]': expected okay

input_5 = "{[]}"
input_str_list = listify(input_5)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '{'
    '{' added. ['{']
    move to next character

current char: '['
    '[' added. ['{', '[']
    move to next character

current char: ']'
    [CORRECT] opening-brace at top-of-stack: [
    '[' removed. ['{']

current char: '}'
    [CORRECT] opening-brace at top-of-stack: {
    '{' removed. []

SYNTAX OK!

3.6. '{([])}': expected okay

input_6 = "{([])}"
input_str_list = listify(input_6)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '{'
    '{' added. ['{']
    move to next character

current char: '('
    '(' added. ['{', '(']
    move to next character

current char: '['
    '[' added. ['{', '(', '[']
    move to next character

current char: ']'
    [CORRECT] opening-brace at top-of-stack: [
    '[' removed. ['{', '(']

current char: ')'
    [CORRECT] opening-brace at top-of-stack: (
    '(' removed. ['{']

current char: '}'
    [CORRECT] opening-brace at top-of-stack: {
    '{' removed. []

SYNTAX OK!

3.7 '1{a(b[2]c)3}4': expected okay

input_7 = "1{a(b[2]c)3}4"
input_str_list = listify(input_7)
tony_linter.lint(input_str_list)
...clearing stack...
empty stack created
current char: '1'
not a brace: skip!

current char: '{'
    '{' added. ['{']
    move to next character

current char: 'a'
not a brace: skip!

current char: '('
    '(' added. ['{', '(']
    move to next character

current char: 'b'
not a brace: skip!

current char: '['
    '[' added. ['{', '(', '[']
    move to next character

current char: '2'
not a brace: skip!

current char: ']'
    [CORRECT] opening-brace at top-of-stack: [
    '[' removed. ['{', '(']

current char: 'c'
not a brace: skip!

current char: ')'
    [CORRECT] opening-brace at top-of-stack: (
    '(' removed. ['{']

current char: '3'
not a brace: skip!

current char: '}'
    [CORRECT] opening-brace at top-of-stack: {
    '{' removed. []

current char: '4'
not a brace: skip!

SYNTAX OK!