Applications of Stack – Expression Conversion and Evaluation

1. Introduction

One of the most important applications of a Stack is the processing of arithmetic and logical expressions.

Stacks are particularly useful for:

• Converting expressions from one notation to another

• Evaluating postfix expressions

• Evaluating prefix expressions

• Managing operators and parentheses

• Checking balanced parentheses

• Supporting compiler and interpreter operations

The three commonly used expression notations are:

1. Infix

2. Prefix

3. Postfix

---

2. Expression

An expression is a combination of operands and operators that represents a computation.

For example:

$$A+B$$

Here:

• A and B are operands.

• + is an operator.

Another example:

$$A+B*C$$

contains:

• Operands: A, B, C

• Operators: +, *

---

3. Operand

An operand is a value, variable, or data item on which an operation is performed.

Examples:

A
B
X
25
100

In:

$$A+B$$

A and B are operands.

---

4. Operator

An operator specifies the operation to be performed on operands.

Common arithmetic operators are:

Operator	Operation	Example
+	Addition	A+B
-	Subtraction	A-B
*	Multiplication	A*B
/	Division	A/B
%	Modulus	A%B
^	Exponentiation	A^B

In C, additional operators such as relational, logical, bitwise, and conditional operators are also available.

For the basic expression-conversion algorithms, arithmetic operators are generally considered.

---

5. Types of Expression Notations

An arithmetic expression can be represented in three major forms:

1. Infix notation

The operator is written between the operands.

Example:

$$A+B$$

2. Prefix notation

The operator is written before the operands.

Example:

$$+AB$$

3. Postfix notation

The operator is written after the operands.

Example:

$$AB+$$

---

6. Infix Expression

In infix notation, the operator is placed between its operands.

Examples:

A + B
A - B
A * B
(A + B) * C
A + B * C

This is the notation normally used by humans in mathematics and programming languages.

Example

$$A+B*C$$

Here, multiplication has higher precedence than addition, so the expression is interpreted as:

$$A+(B*C)$$

---

7. Prefix Expression

In prefix notation, the operator appears before its operands.

It is also called Polish notation.

Examples:

+AB
-AB
*AB

For:

$$A+B*C$$

the prefix form is:

+A*BC

Prefix notation does not require parentheses to indicate the order of operations when the expression is properly formed.

---

8. Postfix Expression

In postfix notation, the operator appears after its operands.

It is also called Reverse Polish notation (RPN).

Examples:

AB+
AB-
AB*

For:

$$A+B*C$$

the postfix form is:

ABC*+

Postfix expressions are particularly convenient for stack-based evaluation.

---

9. Comparison of Infix, Prefix and Postfix

Consider:

$$(A+B)*C$$

Notation	Expression
Infix	(A+B)*C
Prefix	*+ABC
Postfix	AB+C*

Another Example

Consider:

$$A+B*C$$

Notation	Expression
Infix	A+B*C
Prefix	+A*BC
Postfix	ABC*+

---

10. Why Expression Conversion Is Required

Humans generally prefer infix notation, but computers can process expressions efficiently using other representations.

Infix expressions require consideration of:

• Operator precedence

• Associativity

• Parentheses

Stack-based processing can simplify expression conversion and evaluation.

For example:

$$(A+B)*(C-D)$$

can be converted to:

Postfix:

AB+CD-*

The postfix representation makes the evaluation order explicit.

---

11. Operator Precedence

Precedence determines which operator should be evaluated first when an expression contains multiple operators.

For the basic arithmetic operators:

Priority	Operator	Meaning
Highest	^	Exponentiation
High	* / %	Multiplication, Division, Modulus
Low	+ -	Addition, Subtraction

For example:

$$A+B*C$$

Since * has higher precedence than +:

$$A+(B*C)$$

Therefore postfix is:

ABC*+

---

12. Associativity

When two operators have the same precedence, associativity determines the order in which they are processed.

For example:

$$A-B+C$$

The - and + operators have the same precedence and are normally evaluated from left to right:

$$(A-B)+C$$

Common Associativity

Operator	Associativity
+	Left to Right
-	Left to Right
*	Left to Right
/	Left to Right
%	Left to Right
^	Right to Left

The right-to-left associativity of exponentiation is particularly important in expression conversion.

---

13. Role of Parentheses

Parentheses can override normal precedence.

Consider:

$$A+B*C$$

Multiplication is performed first:

$$A+(B*C)$$

But:

$$(A+B)*C$$

requires addition to be performed first.

Thus parentheses have very high priority in expression processing.

---

14. Infix to Postfix Conversion

The stack is used to temporarily store operators and parentheses during conversion.

Basic Rules

While scanning the infix expression from left to right:

1. If the symbol is an operand, add it directly to the postfix expression.

2. If the symbol is an opening parenthesis (, push it onto the stack.

3. If the symbol is a closing parenthesis ), pop operators until ( is encountered.

4. If the symbol is an operator, compare its precedence with the operator on top of the stack.

5. Pop higher- or appropriately equal-precedence operators before pushing the current operator.

6. After scanning the entire expression, pop all remaining operators.

---

15. Algorithm: Infix to Postfix

Algorithm

Input: Infix expression E

Output: Equivalent postfix expression

1. Create an empty stack.
2. Scan the infix expression from left to right.

3. If the scanned symbol is an operand:
       Add it to the postfix expression.

4. If the symbol is '(':
       Push it onto the stack.

5. If the symbol is ')':
       Pop from the stack and add to postfix
       until '(' is found.
       Remove '(' from the stack.

6. If the symbol is an operator:
       While the stack is not empty and
       the operator at the top has higher
       precedence than the current operator
       (or equal precedence when left-associative):
           Pop and add it to postfix.

       Push the current operator.

7. After the expression is completely scanned:
       Pop all remaining operators
       and add them to postfix.

8. Return the postfix expression.

---

16. Example: Infix to Postfix

Convert:

$$A+B*C$$

Step-by-step

Scanned Symbol	Stack	Postfix
A	Empty	A
+	+	A
B	+	AB
*	+ *	AB
C	+ *	ABC
End	Empty	ABC*+

Therefore:

$$\boxed{A+B*C \rightarrow ABC*+}$$

---

17. Example: Infix to Postfix with Parentheses

Convert:

$$(A+B)*C$$

Step-by-step

Symbol	Stack	Postfix
(	(	—
A	(	A
+	( +	A
B	( +	AB
)	Empty	AB+
*	*	AB+
C	*	AB+C
End	Empty	AB+C*

Therefore:

$$\boxed{(A+B)*C \rightarrow AB+C*}$$

---

18. Example: More Complex Infix to Postfix

Convert:

$$A+B*(C-D)$$

Step-by-step

Symbol	Stack	Postfix
A	—	A
+	+	A
B	+	AB
*	+ *	AB
(	+ * (	AB
C	+ * (	ABC
-	+ * ( -	ABC
D	+ * ( -	ABCD
)	+ *	ABCD-
End	—	ABCD-*+

Therefore:

$$\boxed{A+B*(C-D)\rightarrow ABCD-*+}$$

---

19. Complexity of Infix to Postfix Conversion

Suppose the expression contains n symbols.

Each symbol is scanned once.

An operator may be pushed and popped from the stack at most a constant number of times.

Therefore:

Time Complexity

$$\boxed{O(n)}$$

Space Complexity

In the worst case, the stack may contain O(n) operators/parentheses.

$$\boxed{O(n)}$$

---

20. Infix to Prefix Conversion

Infix expressions can also be converted to prefix form.

A common stack-based approach is:

1. Reverse the infix expression.

2. Interchange ( and ).

3. Convert the resulting expression to postfix.

4. Reverse the postfix result to obtain prefix.

Example

Convert:

$$(A+B)*C$$

to prefix.

The result is:

*+ABC

Therefore:

$$\boxed{(A+B)*C \rightarrow *+ABC}$$

---

21. Algorithm: Infix to Prefix

1. Reverse the infix expression.
2. Replace every '(' with ')' and every ')' with '('.
3. Convert the modified expression into postfix
   using a stack.
4. Reverse the resulting postfix expression.
5. The result is the prefix expression.

Complexity

For n symbols:

$$\boxed{Time = O(n)}$$ $$\boxed{Space = O(n)}$$

---

22. Postfix Expression Evaluation

One of the most important applications of a stack is postfix expression evaluation.

Consider:

23+

This represents:

$$2+3=5$$

For postfix evaluation:

• Operands are pushed onto the stack.

• When an operator is encountered, the required operands are popped.

• The operation is performed.

• The result is pushed back onto the stack.

---

23. Algorithm: Postfix Evaluation

Input: Postfix expression

Output: Evaluated result

1. Create an empty stack.

2. Scan the postfix expression from left to right.

3. If the symbol is an operand:
       Push it onto the stack.

4. If the symbol is an operator:
       Pop the top operand.
       Pop the next operand.
       Perform the operation.
       Push the result onto the stack.

5. Repeat until the expression is completely scanned.

6. The final element in the stack is the result.

Important

For a binary operator:

operand2 = pop()
operand1 = pop()

result = operand1 operator operand2

The order is important.

For example:

52-

means:

$$5-2=3$$

not:

$$2-5=-3$$

---

24. Example: Postfix Evaluation

Evaluate:

23*5+

This represents:

$$(2*3)+5$$

Step-by-step

Symbol	Operation	Stack
2	Push	2
3	Push	2, 3
*	2 × 3 = 6	6
5	Push	6, 5
+	6 + 5 = 11	11

Therefore:

$$\boxed{23*5+=11}$$

---

25. Example: Postfix Evaluation with Multiple Operators

Evaluate:

52+83-*

Equivalent expression:

$$(5+2)*(8-3)$$

Step-by-step

Symbol	Operation	Stack
5	Push	5
2	Push	5,2
+	5+2=7	7
8	Push	7,8
3	Push	7,8,3
-	8-3=5	7,5
*	7×5=35	35

Therefore:

$$\boxed{52+83-*=35}$$

---

26. C Program for Postfix Evaluation

The following program evaluates a postfix expression containing single-digit operands.

#include <stdio.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int value)
{
    stack[++top] = value;
}

int pop()
{
    return stack[top--];
}

int evaluatePostfix(char exp[])
{
    int i;
    int operand1, operand2, result;

    for (i = 0; exp[i] != '\0'; i++)
    {
        if (isdigit(exp[i]))
        {
            push(exp[i] - '0');
        }
        else
        {
            operand2 = pop();
            operand1 = pop();

            switch (exp[i])
            {
                case '+':
                    result = operand1 + operand2;
                    break;

                case '-':
                    result = operand1 - operand2;
                    break;

                case '*':
                    result = operand1 * operand2;
                    break;

                case '/':
                    result = operand1 / operand2;
                    break;

                case '%':
                    result = operand1 % operand2;
                    break;
            }

            push(result);
        }
    }

    return pop();
}

int main()
{
    char exp[] = "52+83-*";

    printf("Result = %d\n", evaluatePostfix(exp));

    return 0;
}

Output

Result = 35

Complexity

If the postfix expression contains n symbols:

$$\boxed{Time = O(n)}$$ $$\boxed{Space = O(n)}$$

---

27. Prefix Expression Evaluation

Prefix expressions can also be evaluated using a stack.

Unlike postfix evaluation, prefix expressions are scanned from right to left.

Example

Consider:

+23

This represents:

$$2+3=5$$

---

28. Algorithm: Prefix Evaluation

1. Create an empty stack.

2. Scan the prefix expression from right to left.

3. If the symbol is an operand:
       Push it onto the stack.

4. If the symbol is an operator:
       Pop the first operand.
       Pop the second operand.
       Perform the operation.
       Push the result onto the stack.

5. Continue until the expression is completely scanned.

6. The final element in the stack is the result.

For an operator:

operand1 = pop()
operand2 = pop()

result = operand1 operator operand2

The exact operand order should be handled carefully for non-commutative operations such as subtraction and division.

---

29. Example: Prefix Evaluation

Evaluate:

*+23-84

This represents:

$$(2+3)*(8-4)$$

Step-by-step

Scan from right to left:

Symbol	Operation	Stack
4	Push	4
8	Push	4,8
-	8-4=4	4
3	Push	4,3
2	Push	4,3,2
+	2+3=5	4,5
*	5×4=20	20

Therefore:

$$\boxed{*+23-84=20}$$

---

30. Postfix vs Prefix Evaluation

Feature	Postfix	Prefix
Scanning direction	Left → Right	Right → Left
Data structure	Stack	Stack
Operand	Push	Push
Operator	Pop operands and evaluate	Pop operands and evaluate
Final result	Top of stack	Top of stack
Time complexity	O(n)	O(n)
Auxiliary stack space	O(n)	O(n)

---

31. Expression Conversion and Evaluation: Overall Process

A typical process can be represented conceptually as:

Infix Expression

↓

Expression Conversion

↓

Prefix / Postfix Expression

↓

Stack-Based Evaluation

↓

Final Result

For example:

$$(A+B)*C$$

↓

Postfix:

AB+C*

↓

Evaluation using Stack

↓

Result

---

32. Balanced Parentheses Using Stack

Another important application of stack is checking whether parentheses are properly balanced.

Consider:

(A+B)

This is balanced.

But:

(A+B

is not balanced.

Similarly:

((A+B)*C)

is balanced.

Basic Algorithm

1. Create an empty stack.
2. Scan the expression from left to right.
3. If an opening symbol is found:
       Push it onto the stack.
4. If a closing symbol is found:
       If the stack is empty → Not balanced.
       Otherwise pop the corresponding opening symbol.
5. After scanning:
       If stack is empty → Balanced.
       Otherwise → Not balanced.

The same principle can be extended to:

()
{}
[]

Complexity

For an expression containing n symbols:

$$Time=O(n)$$ $$Space=O(n)$$

in the worst case.

---

33. Important Rules for Expression Conversion

Students should remember these rules:

Rule 1

Operands are normally directly added to the output.

Rule 2

Opening parenthesis ( is pushed onto the stack.

Rule 3

Closing parenthesis ) causes operators to be popped until ( is found.

Rule 4

Higher-precedence operators are processed before lower-precedence operators.

Rule 5

For left-associative operators, an operator of equal precedence on the stack is generally popped before pushing the current operator.

Rule 6

After scanning the complete expression, all remaining operators are popped.

Rule 7

For postfix evaluation, scan left to right.

Rule 8

For prefix evaluation, scan right to left.

---

34. Common Errors in Expression Conversion

Error 1: Ignoring precedence

Incorrect:

A+B*C → AB+C*

Correct:

A+B*C → ABC*+

because * has higher precedence than +.

---

Error 2: Incorrect operand order

For:

52-

correct evaluation is:

$$5-2=3$$

not:

$$2-5=-3$$

---

Error 3: Incorrect handling of parentheses

For:

(A+B)*C

the result is:

AB+C*

not:

ABC+*

---

Error 4: Forgetting remaining operators

After the complete infix expression has been scanned, all operators remaining in the stack must be popped and added to the output.

---

35. Complexity Summary

Let n represent the number of symbols in the expression.

Operation	Time Complexity	Space Complexity
Infix → Postfix	O(n)	O(n)
Infix → Prefix	O(n)	O(n)
Postfix Evaluation	O(n)	O(n)
Prefix Evaluation	O(n)	O(n)
Balanced Parentheses	O(n)	O(n)

The linear time complexity occurs because each expression symbol is processed a limited number of times.

---

36. Applications of Expression Processing

Stack-based expression processing is useful in many areas of computer science:

1. Compilers

Compilers process and transform expressions during syntax and semantic analysis.

2. Calculators

Expression evaluation systems can use stack-based techniques.

3. Programming Languages

Expressions written by programmers must be interpreted according to precedence and associativity rules.

4. Mathematical Software

Symbolic and numerical systems process mathematical expressions.

5. Interpreters

Interpreters evaluate expressions while executing programs.

6. Expression Parsers

Stacks are fundamental to many parsing techniques.

7. Reverse Polish Notation

Postfix expressions are used in systems based on Reverse Polish Notation.

---

37. Important Comparison

Property	Infix	Prefix	Postfix
Operator position	Between operands	Before operands	After operands
Example	A+B	+AB	AB+
Parentheses	Often required	Generally not required	Generally not required
Convenient for humans	Yes	Less common	Less common
Convenient for stack evaluation	Requires conversion/handling	Yes	Yes
Scanning for evaluation	Depends on parsing	Right → Left	Left → Right

---

38. Worked Example for Examination

Convert:

$$A*(B+C)-D$$

to postfix.

Step 1: Scan A

Output:

A

Step 2: Scan *

Push *.

Step 3: Scan (

Push (.

Step 4: Scan B

Output:

AB

Step 5: Scan +

Push +.

Step 6: Scan C

Output:

ABC

Step 7: Scan )

Pop +.

Output:

ABC+

Remove (.

Step 8: Scan -

* has higher precedence than -, so pop *.

Output:

ABC+*

Push -.

Step 9: Scan D

Output:

ABC+*D

Step 10: End of expression

Pop -.

Final postfix:

$$\boxed{ABC+*D-}$$

---

39. Key Points to Remember

• Stack is an important data structure for expression conversion and evaluation.

• The three major notations are infix, prefix, and postfix.

• Infix places the operator between operands.

• Prefix places the operator before operands.

• Postfix places the operator after operands.

• Precedence determines operator priority.

• Associativity determines the processing direction when precedence is equal.

• Infix-to-postfix conversion uses a stack.

• Infix-to-prefix conversion can be performed using reversal and stack-based processing.

• Postfix expressions are evaluated from left to right.

• Prefix expressions are evaluated from right to left.

• During evaluation, operands are pushed onto the stack.

• When an operator is encountered, operands are popped, the operation is performed, and the result is pushed back.

• Expression conversion and evaluation generally require O(n) time.

• Balanced-parentheses checking is another important application of stacks.

---