Iterators - Allowing iteration over data structures (in java)

Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves.

Here's where java gives us the power called iterators which allows us to iterate over data structure.

Design Challenge
Consider the stack data structure and we want to support iteration over it on client side.

Step 1 - Make your stack ADT implement Iterable interface.
What is Iterable?
has a method that returns an Iterator.

public interface Iterable <Type>{
  Iterator <Type>l; iterator();
}

What is Iterator?
Has methods hasNext() and next()

public interface Iterator<Type>{
    boolean hasNext();//tells if it has more element
    Type next();      //gives the next element
    void remove();    //use at your own risk
}

What makes a data structures Iterable?
Once the class implements Iterable interface, one can do following

for(String s:stack)
   print (s);//print each string in stack

here the stack is Stack of strings.
Long hand code to do the same(though not needed in newer versions of java)

Iterator <String> i = stack.iterator();
while(i.hasNext())
{
    String s = i.next();
    print s;
}

Now the class becomes.

Read More

Generic data structures in java

Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this.

Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again.

Attempt 2 - Implement a stack using Object class.
Example

Downside -

• Discover type mismatch errors at run time
• Casting has to be done at client side
• Code looks ugly because of so many castings

Attempt 3 - Java generics

Read More

Evaluating postfix expression using stack

We have seen the conversion of infix to postfix expression here. Now lets  see how to evaluate it.

Algorithm

1. Scan input expression from left to right
• If scanned input is an operand, push it into the stack
• If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack.
2. Repeat above two steps till all the characters are scanned.
3. After all characters are scanned, there will be only one element in the stack, and this is the result of given expression.

Note that here we are having operand stack, but while conversion to postfix from infix, we had operator stack.

Pseudocode
Here is the pseudocode for the same.

evaluatePostfix(postfix) // Evaluates a postfix expression.
valueStack = a new empty stack
while (postfix has characters left to parse)
{ nextCharacter = next nonblank character of postfix
  switch (nextCharacter)
  { 
    case variable:
         valueStack.push(value of the variable nextCharacter)
         break;
  case '+': case '-': case '*': case '/': case '^':
         operandTwo = valueStack.pop()
         operandOne = valueStack.pop()
         result = the result of the operation in nextCharacter and 
                 its operands operandOne and operandTwo
         valueStack.push(result)
         break;
  default: 
       break;
  }
}
return valueStack.peek()

Lets start with infix expression -

2 * (3 + 5) - 6

On post fix conversion -

2 3 5 + * 6 -

Here is how we will proceed

Input token	Operation	Stack contents (top on the right)	Details
2	Push	2
3	Push	2, 3
4	Push	2, 3,5
+	Add	2,8	Pop two values: 3 and 5 and push the result 8.
*	Multiply	16	Pop two values: 2 and 8 and push the result 16.
6	Push	14, 6
-	Subtract	8	Pop two values: 14 and 6 and push result 8
(End of tokens)	Finish	8	Pop the only value 8 and return it

Java code
Here is code in java

   public int calculate(String s)  
   {  
     int n,r=0;  
     n=s.length();  
     Stack a=new Stack(n);  
     for(int i=0;i<n;i++)  
     {  
       char ch=s.charAt(i);  
       if(ch>='0'&&ch<='9')  
         a.push((int)(ch-'0'));  
       else  
       {  
         int x=a.pop();  
         int y=a.pop();  
         switch(ch)  
         {  
           case '+':r=x+y;  
              break;  
           case '-':r=y-x;  
              break;  
           case '*':r=x*y;  
              break;  
           case '/':r=y/x;  
              break;  
           default:r=0;  
         }  
         a.push(r);  
       }  
     }  
     r=a.pop();  
     return(r);  
   }  

Thanks.

References

• http://softwarecave.org/2014/04/03/evaluating-postfix-expressions/
• http://datastructure-using-java.blogspot.in/2010/02/write-java-program-to-evaluate-postfix.html

Read More

Converting an Infix Expression to Postfix expression using a stack

Pre-requisite - What is infix, postfix and prefix?

Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. 
Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation.

Infix - Operators are written in-between their operands. eg.  A+B
Postfix -  Operators are written after their operands.      eg.  AB+    
Prefix - Operators are written before their operands.      eg.  +AB


Here are more examples:

Infix	Postfix	Prefix	Notes
A * B + C / D	A B * C D / +	+ * A B / C D	multiply A and B, divide C by D, add the results
A * (B + C) / D	A B C + * D /	/ * A + B C D	add B and C, multiply by A, divide by D
A * (B + C / D)	A B C D / + *	* A + B / C D	divide C by D, add B, multiply by A

Example taken from http://www.cs.man.ac.uk/~pjj/cs212/fix.html.

Converting infix to postfix expression

Converting and infix expression to postfix or Reverse Polish notation.
I have used a stack ADT developed using a linked list. I prefer linked lists as memory can be allocated dynamically.
One famous algorithm is the Shunting yard algorithm. The approach used in this article is the usual input and stack precedence comparison algorithm.
Precedence values of stack and input characters

Symbols Input Precedence Stack precedence

+,-          1                 2
*,/          3                 4
$,^          6                 5
operands     7                 8
(            9                 0
)            0                 -
#            -                 -1

Pseduocode
To do so, we have to add the operator to the stack, and operands to the string expression, and whenever we find a lower priority operator, we pop out the operator with higher precedence and append to the expression. When whole string expression finishes, we get the postfix expression.

There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

Examples of Pseudocode

Example 1 -  A * B + C
Lets take a simple example - A * B + C , which should evaluate to A B * C  +

	current symbol	operator stack	postfix string
1	A		A
2	*	*	A
3	B	*	A B
4	+	+	A B * {pop and print the '*' before pushing the '+'}
5	C	+	A B * C
6			A B * C +

Example 2 - A + B * C
A + B * C becomes A B C * +
>

	current symbol	operator stack	postfix string
1	A		A
2	+	+	A
3	B	+	A B
4	*	+ *	A B
5	C	+ *	A B C
6			A B C * +

Above examples were taken from http://csis.pace.edu/~wolf/CS122/infix-postfix.htm.
Example 3 - a/b*(c+(d-e))
Consider the following expression -a/b*(c+(d-e))

Suppose a=2, b = 4

Now we do further

Once the conversion, we can evaluate the expression using the stack again.


Implementation in java
Here is java program of the above:

import java.io.*;

class InfPos
{
    private Stack stackADT;
    private String input;
    private String output = "";
    public InfPos(String in)
    {
        input = in;
        stackADT = new Stack();
    }
    public String convert()
    {
        stackADT.push('#');
        System.out.print(stackADT.Peek().item);
         
        for(int j=0; j inpPrec(ch))
            {
                output = output + stackADT.pop().item;
                symbol = stackADT.Peek().item;
            }
            if(stackPrec(symbol) != inpPrec(ch))
                stackADT.push(ch);
            else
                stackADT.pop();
        }
                 
      
        while( !stackADT.isEmpty() )
        {
            if(stackADT.pop().item != '#')
                output = output + stackADT.pop().item;
        }
        return output;
    }
    public int stackPrec(char ch)
    {
        switch(ch)
        {  
            case '+':
            case '-': return 2;
            case '*':
            case '/': return 4;
            case '^':
            case '$': return 5;
            case '(': return 0;
            case '#': return -1;
            default: return 8;
        }
    }
    public int inpPrec(char ch)
    {
        switch(ch)
        {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 3;
            case '^':
            case '$': return 6;
            case '(': return 9;
            case ')': return 0;
            default: return 7;
        }
    }
 
}
class InfixToPostfix
{
    public static void main(String[] args) throws IOException
    {
        String input, output;
        while(true)
        {
            System.out.print("Enter infix: ");
            System.out.flush();
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            input = br.readLine();
            if( input.equals("") )
                break;
            InfPos theTrans = new InfPos(input);
            output = theTrans.convert();
            System.out.println("Postfix: " + output + '\n');
        }
    }
 
} 

Source

Read More

Checking whether the paranthesis are balanced in the expression

Problem

 Checking whether the paranthesis are balanced in the expression

Solution
Method 1 - Using stacks
Stacks can be used to compare the paranthesis.  Whenever we find the opening paranthesis we push it in the stack, and whenever we find closing paranthesis, we pop it out from stack. When the expression finishes and stack is not empty, then it means that paranthesis are not balanced otherwise they are.

Example 1
Consider the following expression {([])}

Example 2

Example 3

Example 4

Pseudocode

Algorithm checkBalance(expression)
// Returns true if the parentheses, brackets, 
    and braces in an expression are paired correctly.
isBalanced = true
while ( (isBalanced == true) and not at end of expression)
{ nextCharacter = next character in expression
 switch (nextCharacter)
 { case '(': case '[': case '{':
   Push nextCharacter onto stack
   break
  case ')': case ']': case '}':
   if (stack is empty)  isBalanced = false
   else
   { openDelimiter = top of stack
    Pop stack
    isBalanced = true or false according to whether openDelimiter and
     nextCharacter are a pair of delimiters
   }
   break
 }
}
if (stack is not empty)  isBalanced = false
return isBalanced

Thanks

Read More

Resizing Array implementation of stack

We have already seen the array implementation of stack, which had one limitation of what happens if data size is bigger than array size, i.e. over flow occurs. To solve this we have to grow our array. But how?

Growing the Array
Approach 1 - Repeated Doubling i.e. Doubling the array every time it is full
We can grow the array by doubling it size, and copying the elements in older array to newer one.
Here is how:

public class ResizingArrayStackOfString {
 String[] s;
 int N;
 public ResizingArrayStackOfString()
 {
  s = new String[1];
 }
 
 public void push(String item)
 {
  if(N==s.length)
   resize(2*s.length);
  s[N++] = item;
 }
 public void resize(int capacity)
 {
  String[] copy = new String[capacity];
  for (int i=0;i<N;i++)
   copy[i]=s[i];
  s = copy;
  
 }
}

Resizing of array takes O(n) time extra, for n elements already inserted.

Shrinking the array
How to shrink the array? Can repeated halving work here. Answer is no.
Suppose the array size is almost full, so we double the array, and again due to some reason stack shrinked, and we shrinked the array by 2, and again only few elements are added such that stack again is full, and again we have to double. So, we have to do it again and again.
    But if we shrink the array size by 4, then atleast we dont have to worry again and again for array size.
Here is how:

 public String pop()
 {
  String item = s[--N];
  s[N] = null;
  if(N>0 && N==s.length/4)
   resize(s.length/2);
  return item;
 }

So we have to make sure that array is between 25% to 100% full.

Time complexity
Push
best case - O(1), worst case - O(N), amortized - O(1)

Pop
best case - O(1), worst case - O(N), amortized - O(1)

size 
O(1) in any case

Memory usage in java
Size varies between 8N to 32N bytes for N elements in stack.

Resizing array vs linked list

Linked list implementation	Resizing array implementation
Every operation takes constant time in worst case	Every operation takes constant amortized time
Extra space and time as we have to deal with links	Less wasted space

Thanks.

Read More

Introduction of Array

This is the basic or simplest type of data structure. An array can be defined as, a list of a finite number "n" of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, ..., n.

If A is chosen for the name of some array, then the elements of A are denoted as,
a1, a2, a3, a4, ..., an
OR  A(1), A(2), A(3), A(4), ..., A(n)
OR  A[1], A[2], A[3], A[4], ..., A[n]

Regardless of the notation, the number K in A[K] is called a subscript and A[K] is called a subscripted variables.

There are some important points related to array:

• Data type may be either fundamental data type or user defined data type.
• Array may be any valid variable name.
• Size of array is numeric value which defines the size of the array.

Array can be 1- dimensional and multidimensional. Usually 2 - dimensional array is called as matrix.

2 - D Array can be implemented in memory in 2 ways:

1. Row major order implementation
2. Column major order implementation

Read More