General Advice when solving problems

• Understand the problem being asked
• Don’t forget to handle edge cases
• Expressing your answer is just as important as understanding the problem, and solving it!

Problems with Stacks #

Checking parenthesis #

Examples:

Input: ()
Output: true

Input: ()[]{}
Output: true

Input: ([)]
Output: false

Input: {[]}
Output: true

Input : {[]{()}}
Output : true

Input : [{}{}(]
Output :false

The logic here is to push a new item on to a stack when we notice an input with an opener, and pop when there is a closer.

# Python3 code to Check for balanced parentheses in an expression
open_list = ["[","{","("]
close_list = ["]","}",")"]

# Function to check parentheses
def check(myStr):
    stack = []
    for i in myStr:
        if i in open_list:
            stack.append(i)
        elif i in close_list:
            pos = close_list.index(i)
            if ((len(stack) > 0) and
                (open_list[pos] == stack[len(stack)-1])):
                stack.pop()
            else:
                return "Unbalanced"
    if len(stack) == 0:
        return "Balanced"
    else:
        return "Unbalanced"

Sample code

string = "{[]{()}}"
print(string,"-", check(string))

string = "[{}{})(]"
print(string,"-", check(string))

string = "((()"
print(string,"-",check(string))

Evaluate Postfix Notation #

Given a valid expression in reverse polish notation, evaluate it and return the result.

Input: ["2", "1", "+", "3", "*"]
Output: 9, because ((2 + 1) * 3) = 9

Input: ["4", "10", "5", "/", "+"]
Output: 6, because (4 + (10 / 5)) = 6

The algorithm #

• Create an empty stack and scan postfix expression from left to right
• If element is an operand, push it into the stack
• If the element is an operator 📦:
  • pop twice to get A and B (calculate B 📦 A)
  • push result back to the stack
• When expression is ended, the value in stack is the final answer

Example #

\[ \(3 1 + 9 *\) \vspace{1in} 36

\begin{tikzpicture} \matrix[matrix of nodes, %draw, nodes in empty cells, nodes={minimum size=10mm}]{ % column sep=-\pgflinewidth Postfix char read in & Operands (stack) & Actions \\\
3 & 3 & \\\
1 & 3 1 & \\\
$+$ & 4 & Pop the top 2 operands and push the result \\\
9 & 4 9 & \\\
$*$ & 36 & Pop the top 2 operands and push the result \\\
}; The expression evalutes to 36. \end{tikzpicture}

\fi ]