Evaluating Postfix Expression


Evaluating a postfix expression involves iterating through each symbol in the expression and performing operations based on whether the symbol is an operand or an operator. Here's a simple algorithm to evaluate a postfix expression:

Algorithm
1.Initialize an empty stack.

2.Scan the expression from left to right:
  •     For each symbol in the expression:If it's an operand (a number), push it onto the stack.
    If it's an operator:
  •     Pop the required number of operands from the stack (e.g., two operands for binary operators).
  •     Perform the operation using the operator and operands.
  •     Push the result back onto the stack.

3.After scanning the entire expression, the result should be on the top of the stack. Pop it to get the final result.

Example:

Expression: 23*5+

Symbol: 2
Stack: [2]

Symbol: 3
Stack: [2, 3]

Symbol: *
Pop two operands (3 and 2), perform 3 * 2, and push the result (6) back.
Stack: [6]

Symbol: 5
Stack: [6, 5]

Symbol: +
Pop two operands (5 and 6), perform 5 + 6, and push the result (11) back.
Stack: [11]

At this point, the expression is fully evaluated, and the result (11) is at the top of the stack.

So, the stack content during the evaluation of 23*5+ was as follows:[2]
[2, 3]
[6]
[6, 5]
[11]

After the entire expression is processed, the final result (11) is at the top of the stack.
Example:5 2 3 - + 2/ ( University Question)
Symbol:5
Stack: [5]
 
Symbol:2
Stack: [5,2]
 
Symbol:3
Stack: [5,2,3]
 
Symbol: -
Pop two operands (2 and 3), perform 2 - 3, and push the result (-1) back.
Stack: [5,-1]
 
 
Symbol:+
Pop two operands (5 and -1), perform 5 - 1, and push the result (4) back.
Stack: [4]
 
Symbol:2
Stack: [4,2]
 
 
Symbol:/
Pop two operands (4 and 2), perform 4/2, and push the result (2) back.
Stack: [2]
 
After the entire expression is processed, the final result (2) is at the top of the stack.

C Program- Evaluation of Postfix Expression
/****************************************************************************/
#include <stdio.h>
#include <ctype.h>

#define MAXSTACK 100 
#define POSTFIXSIZE 100 

/* declare stack and its top pointer to be used during postfix expression
evaluation*/
int stack[MAXSTACK];
int top = -1; 
/* define push operation */
void push(int item)
{

    if (top >= MAXSTACK - 1) {
        printf("stack over flow");
        return;
    }
    else {
        top = top + 1;
        stack[top] = item;
    }
}

/* define pop operation */
int pop()
{
    int item;
    if (top < 0) {
        printf("stack under flow");
    }
    else {
        item = stack[top];
        top = top - 1;
        return item;
    }
}

/* define function that is used to input postfix expression and to evaluate it */
void EvalPostfix(char postfix[])
{

    int i;
    char ch;
    int val;
    int A, B;

    /* evaluate postfix expression */
    for (i = 0; postfix[i] != '$'; i++) {
        ch = postfix[i];
        if (isdigit(ch)) {
            /* we saw an operand,push the digit onto stack
ch - '0' is used for getting digit rather than ASCII code of digit */
            push(ch - '0');
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            /* we saw an operator
* pop top element A and next-to-top elemnet B
* from stack and compute B operator A
*/
            A = pop();
            B = pop();

            switch (ch) /* ch is an operator */
            {
            case '*':
                val = B * A;
                break;

            case '/':
                val = B / A;
                break;

            case '+':
                val = B + A;
                break;

            case '-':
                val = B - A;
                break;
            default:
                printf("Invalid operator\n");
                exit(1);
            }

            /* push the value obtained above onto the stack */
            push(val);
        }
    }
    printf(" \n Result of expression evaluation : %d \n", pop());
}

int main()
{

    int i;

    /* declare character array to store postfix expression */
    char postfix[POSTFIXSIZE];
    printf("ASSUMPTION: There are only four operators(*, /, +, -) in an expression and operand is single digit only.\n");
    printf(" \nEnter postfix expression,\npress right parenthesis '$' for end expression : ");

    /* take input of postfix expression from user */

    for (i = 0; i <= POSTFIXSIZE - 1; i++) {
        scanf("%c", &postfix[i]);

        if (postfix[i] == '$') 
        {
            break;
        } 
    }

    /* call function to evaluate postfix expression */

    EvalPostfix(postfix);

    return 0;
}





Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more