Stacks

Stack is a container which supports retrieval by last-in, first out (LIFO) order. Imagine a pile of books stacked on top of one another. If you want to add a new book it always goes to the top. If you want to remove a book then it comes from the top. The book that got added recently is the one that gets removed first. Hence the operation on a stack is called as LIFO.

stackofbooks

Key Operations on a Stack

Here are the key operations that are available in a stack

Operation Description Time
push(e) Adds an element e to the top of the stack O(1)
pop() Removes an element from the top of the stack O(1)
peek() Returns the element from the top of the stack without removing it O(1)

Implementation of a Stack

Given below is a simple implementation of stack in Python. It uses list as the underlying data structure.

class Stack:

	def __init__(self):
		self.elements = []

	def push(self, element):
		self.elements.append(element)

	def pop(self):
		return self.elements.pop()

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

	def size(self):
		return len(self.elements)

	def isEmpty(self):
		return self.elements == []

Problem 1: Check if the symbols are balanced

Most of the programming languages uses symbols [] and (). These languages need a way to check if they are balanced. How do you solve this problem? Let us look at some examples of balanced and unbalanced symbols.

[]       - Balanced
[()]     - Balanced
[([()])] - Balanced
[)       - Unbalanced
[(       - Unbalanced
[(])     - Unbalanced

From the above examples we can conclude that for the symbols to be balanced

  1. The total number and type of open symbols should match the total number and type of closed symbols. For each [ there should be a matching ] and for each ( there should be a matching )
  2. A closed symbol should match the last open symbol.
[ ( [ ( ) ] ) ]
1 2 3 4 5 6 7 8

In the above example look at item no 5 ) it is a match for item 4 which is the recent open item. Similarly look at item 6 ] it is a match for second recent open item 3. The order in which the symbols are matched are in the reverse of the order in which they are encountered. This is what stack does and we can solve the problem using a stack in an elegant way.

def isSymbolsBalanced(symbols):
	openSymbols = "(["
	closedSymbols = ")]"
	s = Stack()
	for p in symbols:
		#Open symbol push it to stack
		if p in openSymbols:
			s.push(p)
		else:
			topItem = s.pop()
			#Open and closed symbol does not match.
			if closedSymbols.index(p) != openSymbols.index(topItem):
				return False

	# At this point the stack should be empty.
	if s.isEmpty():
		return True

	# The Symbols are not balanced.
	return False

Problem 2: Convert an infix to a postfix expression

Consider the following expression 1 + 2. In this the operator appears between the operands. This expression is called as infix expression. Take a look at 1 + 2 * 3. What is the result of this expression?

1 + 2 * 3 = 3 * 3 = 9 (incorrect)

OR

1 + 2 * 3 = 1 + 6 = 7 (correct)

The correct answer is 7. Each operator has a precedence. * and / has an higher precedence than + and -. Hence we need to do the * operation first followed by +. What if you want to the addition operation to be done first. You can use the operator () to alter the precedence.

(1 + 2) * 3 = 3 * 3 = 9

Human brain can deal with an infix expression easily. What if you want to write a computer program to evaluate this expression. It is hard to write a program to evaluate an infix expression. Is there is a better way to represent? Turns out that there are two other ways to represent an expression. They are called as prefix and postfix expressions. If the operators appear before the operand then it is called as prefix expression. If the operators appear after the operand then it is called as postfix expression. The biggest advantage is there are no (). The position of the operators determine the order in which they gets evaluated. Given below are examples of converting the expressions.

Infix Prefix Postfix
1 + 2 +12 12+
1 + 2 * 3 +1*23 123*+
1 * 2 + 3 +*123 12*3+
(1 + 2) * 3 *+123 12+3*
( 1 + 2 ) * ( 3 + 4 ) – ( 5 + 6 ) -*+12+34+56 12+34+*56+-

Given below is the code which does the infix to postfix conversion.

def infixToPostfixConversion(expression):
	operators = '*/+-'
	precedence = {'*' : 100, '/' : 100, '+' : 1, '-' : 1, '(' : 0}
	numbers = '0123456789'
	output = []
	s = Stack()
	exprList = expression.split(' ')
	for e in exprList:
		if e in numbers:
			output.append(e)
		else:
			if e == '(':
				s.push(e)
			elif e == ')':
				top = s.pop()
				while top != '(':
					output.append(top)
					top = s.pop()
			elif e in operators:
				# Honor operator precedence.
				while (s.isEmpty() == False) and (precedence[s.peek()] > precedence[e]):
					output.append(s.pop())
				s.push(e)

	# Add the reamining items in the stack to the output list.
	while s.isEmpty() == False:
		output.append(s.pop())

	return " ".join(output)

Problem 3: Evaluate a postfix expression

Evaluation of an postfix expression is very easy if stack is used. Also you need not worry about precedence as the position of the operator is based on its precedence.

def evaluatePostfixExpression(expression):
	numbers = '0123456789'
	s = Stack()
	expressionList = expression.split(' ')
	for e in expressionList:
		if e in numbers:
			s.push(e)
		else:
			operand2 = int(s.pop())
			operand1 = int(s.pop())
			if e == '+':
				s.push(operand1 + operand2)
			elif e == '-':
				s.push(operand1 - operand2)
			elif e == '*':
				s.push(operand1 * operand2)
			else:
				s.push(operand1 / operand2)
	return s.pop()

Given below is the output for converting an infix to postfix expression and then evaluating the postfix expression.

print infixToPostfixConversion('( 1 + 2 ) * ( 3 + 4 ) - ( 5 + 6 )')
The output is: 1 2 + 3 4 + * 5 6 + -

when this is passed as input to evaluatePostfixExpression('1 2 + 3 4 + * 5 6 + -')
The output is: 10
Advertisements

One thought on “Stacks

Comments are closed.