Conversion of Arithmetic Expression Using Stack

Stack has various application as we have discussed in the previous post. In this post, we will see how stack is useful to convert the user input expression into a meaningful result.

There are basically three types of expression:

  1. Infix expression
  2. Postfix expression
  3. Prefix expression
We generally write any equation in the form of infix expression, but computer system convert this expression into Post-fix or Prefix expression for evaluating the results.

Example: Infix expressions:      A+B , X*(Y+Z)
                Postfix expression:    AB+ , XYZ+*
                Prefix expression:     +AB, *X+YZ

The transformation  of any Infix expression into Postfix expression is performed based on the precedence of the operators. 

  • The higher precedence operator evaluation is performed first, later the others operators. 
  •  If two operator precedence is equal then we will evaluate the expression left to right,  whichever operator coming first evaluate it.
Operator Precedence:

Lets see some examples:
Infix:     (A+B)*(C-D)
Postfix:            ?

To convert this expression into Postfix, we will use the Stack data structure. 
  1. Scan the expression left to right
  2. Operator insert into the stack
  3. Operand write in the Postfix column
  4. Before insert the operator within the stack check its precedence.
  5. If higher precedence operator in the stack, then pop the operator first 
  6. Later, Push the lower precedence operator.
 Example 1:                            Infix->  (A+B)*(C-D)

INPUT                                             STACK                                            POSTFIX

Initially                                               Empty                                               Empty
(                                                           (                                                        Empty
A                                                         (                                                            A
+                                                          (+                                                         A
B                                                         (+                                                          AB
)                                        PoP all the Operators before (                                AB+
*                                                          *                                                           AB+
(                                                          *(                                                          AB+
C                                                         *(                                                         AB+C
-                                                          *(-                                                        AB+C
D                                                        *(-                                                        AB+CD
)                                        PoP all the Operators before (                              AB+CD-
                                                   PoP * Operator                                           AB+CD-*
_____________________________________________________________________


Example 2:                      Infix-> A*(B+C)/D

INPUT                                            STACK                                             POSTFIX___

Initially                                             Empty                                                   Empty
A                                                       Empty                                                       A
*                                                           *                                                             A
(                                                          *(                                                              A
B                                                        *(                                                               AB
+                                                         *(+                                                            AB
C                                                         *(+                                                           ABC
)                                    PoP all the Operators before (                                       ABC+
/    Equal precedence Operator Left->Right * is first POP and PUSH /       ABC+*
D                                                         /                                                              ABC+*D
                                                        POP /                                                          ABC+*D/      
______________________________________________________________________

Example 3:                                Infix-> (A+(B*C))

INPUT                                               STACK                                            POSTFIX____

Initially                                              Empty                                                 Empty
(                                                             (                                                       Empty
A                                                            (                                                           A
+                                                            (+                                                         A
(                                                             (+(                                                        A
B                                                            (+(                                                       AB
*                                                             (+(*                                                     AB
C                                                            (+(*                                                     ABC
)                                            PoP the operators before (                                    ABC*
)                                            PoP the Operators before (                                   ABC*+

________________________________________________________________________

Comments

Post a Comment

Popular posts from this blog

Types of Algorithm and Its Complexity Analysis

Image
In this post, we will learn types of Algorithm and its time complexity analysis with examples  An algorithm is divided into two forms called iterative and recursive, as shown above. Firstly, we analyze the time complexity of the iterative algorithm and then recursive. Example 1:                           A()                           {                            int i;                            for(i=1 to n)   % loop run n times                            pf("deepa");                           } First, the above function is fall into the independent category. Hence, the running time of the loop will be n and it print the particular name n times. Therefore, the worst case time complexity of this algorithm will be O(n). Example 2:                          A()                         {                         int i;                         for(i=1, i^2<=n, i++)                         printf("deepa");                         } Similarly
Read more

First Step of Problem Solving Using Data Structure and Algorithm

Image
What is problem ? A state of difficulty that need to be resolve A problem exist and its solution needs to be  attain either correct or incorrect A problem gives an opportunity to improve the current state A problem is a difference between the  current state and goal state Problem Faced in daily life        Like making the decisions what should i wear today to look good? what career? what job? what shoes? what course? What happens when bad decisions are made ? Wastage of time and resource   Six steps to ensure  a Best decision in PROBLEM SOLVING Identify the problem first understand the problem Identify the different way to solve the problem (efficient) Select the best one solution among the various alternative solutions Identify the list of steps to solve a problem (instructions) Evaluate the solution of given problem (different set of inputs) Take the problem of and apply the six step of problem solving     A   Water Jug Pro
Read more

Asymptotic Notations

Image
 In computer science, any problem can be solved using the programming language. And a particular problem can have multiple solutions in terms of Algorithm. To find out which one is the best algorithm for a problem, we analyse it in terms of time and space.  To define the time and space complexity of an algorithm, we use the Asymptotic notation. Mostly three types of Asymptotic notation is widely preferred to represent the complexity of the algorithm. Big-O mathematically represented as O The X-axis of the above graph showing the size of the input (n) and Y axis showing the increase in  time (t) . In the graph,   f(n) function showing the increase of time as input   size   n is increasing for a particular algorithm. Beside, the another function called cg(n) showing the worst case of f(n) . Hence, in the above graph cg(n)  is above the f(n). If we bound the time complexity or f(n) of a given algorithm in terms of input n with another function called cg(n) for all
Read more