Competitive Python

In this post we will explore and implement an algorithm which helps us verify that if the brackets are balanced or validly used. This is a very important application of stacks as a lot of programming languages use brackets very extensively in their syntax and one of the job of a compiler is to check if the brackets are balanced or not. For simplicity's sake we will just use a list with the methods append() and pop(). This will help us emulate a stack without actually needing to implement it. If you want to, you can go and learn about stacks on this link . A set of brackets can be called balanced if all of the brackets in it are properly matched. Examples of balanced brackets : (([]{}{})) ({{}}[]) Examples of unbalanced brackets : (([)]) {{}]}]]) So now getting to the algorithm, what we simply do is that we go through a string of brackets and check that for every closing bracket there is a properly nested opening bracket. This is how we do it - Convert the input string into a...

We are going to look at Dijkstra's two-stack algorithm and see how it's implemented. This algorithm is used to evaluate infix expressions. It uses stacks at its core, so if you don't know about stacks or if you'd want to learn more about them, click this link There are three types of expressions, Infix : Infix expressions are the ones where the operators are used between values, like a + b - c . Postfix : These are the expressions where operators are written after the values, like a b c +- , this translates to a + b - c in infix. Prefix : In these expressions, the operators are written before the values, for example + - a b c . This expression will also be equal to a + b - c in infix. Okay, so what this algorithm does is evaluate expressions like ( ( 3 + 4 ) * 83 ) . It starts by breaking down this expression into a list of stings and create two empty stack, one for housing the values and other for the operators. Then we go through the list one by one. Whenev...

Stack So, now we're going to talk about stack , a linear data structure and also we will see its implementation. In another post which will be linked below later will discuss its uses. So what is a stack ? Visualise a pile of coins or a stack of trays put one over the other. The item that has been put at the last has to be removed first as it is over all the other items. Hence, it is a data structure that works on LIFO (Last in First out) principle. Which simply means that the element that has been added the last will be removed first. It is a very useful data structure and has several applications like expression evaluation and HTML validat or or a bracket matching verifier . In this data structure we only have operations that take their effect only at one end of the list. Both, the front or the end of a list can be used to implement it but using the tail(back-end) of the list is more efficient. The main operation or methods on a stack are - Push : Adds element at the...