Evaluate Postfix Expression Using Stack in DSA C - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: You are building a simple calculator that reads a postfix expression (also called Reverse Polish Notation) and calculates the result. Postfix expressions are used in calculators and computer programs to avoid confusion with parentheses.Example: The postfix expression 23+ means 2 + 3, which equals 5.

🎯 Goal: Build a program that uses a stack to evaluate a postfix expression containing single-digit numbers and the operators +, -, *, and /.

📋 What You'll Learn

Create a stack to hold integer values

Read a postfix expression as a string

Use a loop to process each character in the expression

Push numbers onto the stack

Pop two numbers when an operator is found and apply the operator

Push the result back onto the stack

Print the final result after processing the entire expression

💡 Why This Matters

🌍 Real World

Postfix expressions are used in calculators and computer programs to simplify expression evaluation without parentheses.

💼 Career

Understanding stack-based expression evaluation is important for programming language interpreters, compilers, and calculator apps.

1

Create the postfix expression string

Create a character array called postfix and initialize it with the string "231*+9-" which represents the postfix expression.

DSA C

# Create the postfix expression string
# Your code here

Hint

Use double quotes to create a string in C and assign it to postfix.

2

Create a stack and a top index

Create an integer array called stack with size 100 and an integer variable called top initialized to -1 to represent an empty stack.

DSA C

char postfix[] = "231*+9-";
// Create stack array and top variable
# Your code here

Hint

The stack is an integer array and top keeps track of the last filled position.

3

Write the loop to evaluate the postfix expression

Write a for loop using an integer i to iterate over each character of postfix until the null character '\0'. Inside the loop, if the character is a digit, push its integer value onto stack and increment top. If it is an operator (+, -, *, /), pop the top two values from stack, apply the operator, and push the result back onto stack. Use top to manage the stack positions.

DSA C

char postfix[] = "231*+9-";
int stack[100];
int top = -1;

// Loop through postfix expression and evaluate
# Your code here

Hint

Use ASCII values to convert characters to integers. Remember to pop two values for operators and push the result back.

4

Print the final result from the stack

Print the top value of the stack using printf with the format "%d\n". This value is the result of the postfix expression evaluation.

DSA C

char postfix[] = "231*+9-";
int stack[100];
int top = -1;

for (int i = 0; postfix[i] != '\0'; i++) {
    char ch = postfix[i];
    if (ch >= '0' && ch <= '9') {
        stack[++top] = ch - '0';
    } else {
        int val2 = stack[top--];
        int val1 = stack[top--];
        int result;
        if (ch == '+') result = val1 + val2;
        else if (ch == '-') result = val1 - val2;
        else if (ch == '*') result = val1 * val2;
        else if (ch == '/') result = val1 / val2;
        stack[++top] = result;
    }
}

// Print the final result
# Your code here

Hint

The final result is the only value left on the stack at position top.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Stack

B. Queue

C. Array

D. Linked List

Solution

1. Step 1: Understand postfix evaluation process

   Postfix expressions are evaluated by scanning from left to right and using a data structure to store operands temporarily.

2. Step 2: Identify the suitable data structure

   A stack is used because it allows pushing operands and popping them when an operator is encountered, following Last-In-First-Out order.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Postfix evaluation uses stack = Stack [OK]

Hint: Remember: postfix needs LIFO, so use stack [OK]

Common Mistakes:

• Confusing stack with queue
• Using array without stack operations
• Thinking linked list is primary for postfix

2. Which of the following is the correct syntax to push an integer value 'x' onto a stack named 's' in C?

easy

A. stack_push(x);

B. s.push(x);

C. push(x, s);

D. push(s, x);

Solution

1. Step 1: Understand typical stack push function signature

   In C, stack push usually takes the stack and the value to push as arguments, e.g., push(stack, value).

2. Step 2: Match the correct syntax

   push(s, x); matches the common pattern push(s, x); where 's' is the stack and 'x' is the value.

3. Final Answer:

   push(s, x); -> Option D

4. Quick Check:

   push(stack, value) = push(s, x) [OK]

Hint: Remember: push(stack, value) in C [OK]

Common Mistakes:

• Using object.method() syntax in C
• Swapping argument order
• Using undefined function names

3. What is the result of evaluating the postfix expression "6 2 3 + -" using a stack?

medium

A. 3

B. 1

C. 5

D. -1

Solution

1. Step 1: Evaluate postfix step-by-step

   Push 6, push 2, push 3. Encounter '+', pop 3 and 2, add: 2+3=5, push 5. Encounter '-', pop 5 and 6, subtract: 6-5=1.

2. Step 2: Verify final stack value

   After all operations, the stack has one value: 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   6 - (2 + 3) = 1 [OK]

Hint: Process operators by popping two operands [OK]

Common Mistakes:

• Subtracting in wrong order (operand2 - operand1)
• Adding instead of subtracting
• Not pushing intermediate results

4. Identify the error in this C code snippet for postfix evaluation:

char* expr = "5 9 8 + 4 6 * * 7 + *";
int i = 0;
while(expr[i] != '\0') {
  if(isdigit(expr[i])) push(stack, expr[i]);
  else { /* operator handling */ }
  i++;
}

medium

A. Pushing character digit instead of integer value

B. Using while loop instead of for loop

C. Missing stack initialization

D. Incorrect operator handling

Solution

1. Step 1: Check what is pushed onto stack

   The code pushes expr[i], which is a character like '5', not the integer 5.

2. Step 2: Explain why this is wrong

   Characters have ASCII codes; pushing '5' pushes 53, not integer 5, causing wrong calculations.

3. Final Answer:

   Pushing character digit instead of integer value -> Option A

4. Quick Check:

   Push integer, not char digit [OK]

Hint: Convert char to int before push: expr[i] - '0' [OK]

Common Mistakes:

• Pushing char instead of int
• Ignoring spaces in expression
• Not handling operators properly

5. Given the postfix expression "4 5 7 2 + - *", what is the final evaluated result using stack evaluation?

hard

A. -24

B. 16

C. -16

D. 24

Solution

1. Step 1: Evaluate inner expression 7 2 +

   Push 4, 5, 7, 2. '+' operator: pop 2 and 7, add 7+2=9, push 9.

2. Step 2: Evaluate next operator '-'

   Next operator '-', pop 9 and 5, subtract 5-9 = -4, push -4.

3. Step 3: Evaluate final operator '*'

   Pop -4 and 4, multiply 4 * -4 = -16, push -16.

4. Final Answer:

   -16 -> Option C

5. Quick Check:

   4 * (5 - (7 + 2)) = -16 [OK]

Hint: Evaluate inner expressions first, then combine [OK]

Common Mistakes:

• Wrong operator order in subtraction
• Not evaluating nested operations correctly
• Mixing up operand order in multiplication