Checking Balance of Symbols in a expression

This article is part of article series - "Datastructures"

A balanced expression contains right number of closing and open braces.

For example:

• [[ - unbalanced expression
• []{}() - balanced expression
• [(*)] - balanced expression

Let us see how to find if an expression is balanced or not by checking for following operators [ ] { } and ( ) in the given expression.

Using Stacks

Conversion from Infix to Postfix

This article is part of article series - "Datastructures"

Converting a Fully Parenthesized Infix expression into Postfix expression  

Analysis:

Five types of input characters

• Opening parentheses
• Operands
• Operators
• Closing parentheses
• New line character (\n)

Pseudocode:

********************************************************  
 Function  : main  
  
 Calls     : createStack  
             freeStack                
             pushIntoStack   
             popFromStack   
  
 Called by : NONE   
  
 Input   
 Parameters: Accepts input expression for processing  
    
 Returns   : Converts Fully paranthesized INFIX 
             expression into POSTFIX expression
******************************************************** 

SET i to 0
GET infix expression from user into input_array
SET var with input_array[i]

CALL createStack

WHILE var != end of string

  IF var equals to '(' THEN
  
    CALL pushIntoStack (stack, var)  

  ELSE IF var is a number THEN        
  
    PRINT var  

  ELSE IF var is an arithmetic operator THEN
  
    CALL pushIntoStack (stack, var) 
    
  ELSE IF var equals to ')' THEN

    WHILE stackTop != '('

      IF stackTop is an arithmetic operator THEN

        PRINT stackTop
        popFromStack (stack)

      ENDIF
    
    ENDWHILE

    popFromStack (stack)

  ENDIF

  SET var with input_expression[INCREMENT i]

ENDWHILE

CALL freeStack (stack)

Implementation of Stack using Singly Linked Lists

Stacks are linear data structures which means the data is stored in what looks like a line (although vertically). In simple words we can say

A stack is a last in, first out (LIFO) abstract data type and data structure.

Basic usage of stack at the Architecture level is as a means of allocating and accessing memory.

We can only perform two fundamental operations on a stack: push and pop.

The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it.