Stack, Implementation in Dart and Python, And how to use them to solve problems.

On my way to understanding DS & Algorithms, I choose to read the book "Data Structures Algorithms in Dart" and "Problem Solving with Algorithms and Data Structures Using Python". Fortunately, these two Books begin with Stack.

What is a Stack?

A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top.” The end opposite the top is known as the “base.” The base of the stack is significant since items stored in the stack closer to the base represent those that have been in the stack the longest. The most recently added item is the one that is in a position to be removed first. This ordering principle is sometimes called LIFO, last-in-first-out. It provides an ordering based on the length of time in the collection. Newer items are near the top, while older items are near the base.

Now that we know what is Stack let's try to implement it with Python and Dart

Implementation in Python and Dart

Python

class Stack:

? ? def __init__ (self):
? ? ? ? self.items =[]

? ? def is_empty (self):
? ? ? ? return self.items == []

? ? def push (self, item):
? ? ? ? self.items.append (item)

? ? def pop (self):
        return self.items.pop ()

    def peek (self):
        return self.items[len (self.items) - 1]

  ? def size (self):
        return len (self.items)        

Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.

There are only two essential operations for a stack:

? push: Add an element to the top of the stack.

? pop: Remove the top element of the stack.

Dart

class Stack<E> {

  final List _storage;
  Stack() : _storage = [];
  //Push and Pop Operations
  void push(E element) => _storage.add(element);

  E pop() => _storage.removeLast();


  //Non-Essential Operations
  E get peek => _storage.last;
  bool get isEmpty => _storage.isEmpty;
  bool get isNotEmpty => !isEmpty;
          
  }        

Now we need to solve problems with Stack.

how to use them to solve problems.

the Problem is Matching Parentheses

(()()()()) // return True

(((()))) // return True

(()((())())) // return True

Compare those with the following, which are not balanced:

((((((()) // False

())) // False

(()()(() // False

The function takes a String of Parentheses and checks if the Parentheses are balanced

1 import Stack #import the Stack class as previously defined 
2 
3 def par_checker(symbol_string): 
4     s = Stack() 
5     balanced = True 
6     index = 0 
7     while index < len(symbol_string) and balanced: 
8         symbol = symbol_string[index] 
9         if symbol == "(": 
10            s.push(symbol) 
11        else: 
12            if s.is_empty(): 
13                balanced = False 
14            else: 
15                s.pop() 
16 
17        index = index + 1 
18 
19    if balanced and s.is_empty(): 
20        return True 
21    else: 
22        return False 
23 
24 print(par_checker('((()))'))  // True
25 print(par_checker('(()')).    // False        

now let's be more general with Balanced Symbols

The balanced parentheses problem shown above is a specific case of a more general situation that arises in many programming languages. The general problem of balancing and nesting different kinds of opening and closing symbols occurs frequently. For example, in Python square brackets, [ and ], are used for lists; curly braces, { and }, are used for dictionaries; and parentheses, ( and ), are used for tuples and arithmetic expressions. It is possible to mix symbols as long as each maintains its own open and close relationship. Strings of symbols such as

{ { ( [ ] [ ] ) } ( ) } // true

[ [ { { ( ( ) ) } } ] ] // true

[ ] [ ] [ ] ( ) { } // true

are properly balanced in that not only does each opening symbol have a corresponding closing symbol, but the types of symbols match as well.

Compare those with the following strings that are not balanced:

( [ ) ] // false

( ( ( ) ] ) ) // false

[ { ( ) ] // false

let's do it with Dart this time

class Solution 
? ?bool equals(String open, String close){
? ? ? ?String opens = "([{";
? ? ? ?String closes = ")]}";
? ? ? ?return opens.indexOf(open) == closes.indexOf(close);
? ?}?
? bool isValid(String s) {
? ? ? var stack = Stack();
? ? ? bool balanced = true;
? ? ? int index = 0;
? ? ? while (index < s.length && balanced)
? ? ? {
? ? ? ? ? ? String symbol = s[index];
? ? ? ? ? ? if (? "([{".contains(symbol))
? ? ? ? ? ? ? ? stack.push(symbol);
? ? ? ? ? else
? ? ? ? ? {
? ? ? ? ? ? ? if (stack.isEmpty)
? ? ? ? ? ? ? ? ? balanced = false;
? ? ? ? ? ? ? else
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? String top = stack.pop();
? ? ? ? ? ? ? ? ? if (!equals(top, symbol))
? ? ? ? ? ? ? ? ? ? ? balanced = false;
? ? ? ? ? ? ? }??
? ? ? ? ? ? ??
? ? ? ? ? }
? ? ? ? ? ? ??
? ? ? ? index++;? ? ? ? ??
? ? ? }
? ? if (balanced && stack.isEmpty)
? ? ? ? return true;
? ? else
? ? ? ? return false;


? }
? ?
}        

the best thing when understanding Algorithms you can solve problems you can do it before like that