1.
Use a stack to evaluate infix expression and convert into postfix
Stack is used twice:
1. For conversion
2. For evaluation
Operator precedence:
() > ^ > * / > + -
Algorithm: INFIX POSTFIX
1. Scan infix expression left to right
2. If operand add to postfix
3. If ( push
4. If ) pop until (
5. If operator pop higher precedence operators
6. Push current operator
7. Repeat
8. Pop remaining elements
Algorithm: POSTFIX EVALUATION
1. Scan postfix expression
2. If operand push
3. If operator:
o Pop two operands
o Apply operation
o Push result
4. Final value = result
STEPS
Step 1: Convert Infix Postfix
Examples:
A+B* C ABC*+
(2+3)*(4+5)
Infix expression: (2+3)*(4+5)
Postfix expression: 23+45+*
Evaluation result: 45
Rules:
● Operand directly add to postfix
● ( push to stack
● ) pop until (
● Operator pop higher/equal precedence operators from stack
Step 2: Evaluate Postfix
● Scan postfix expression
● If operand push
● If operator pop two operands and apply operation
PROGRAM
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Stack operations
void push(char x)
{
stack[++top] = x;
char pop()
return stack[top--];
int priority(char x)
if (x == '(')
return 0;
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/')
return 2;
if (x == '^')
return 3;
return 0;
// Infix to Postfix
void infixToPostfix(char infix[], char postfix[])
{
int i = 0, j = 0;
char x;
while (infix[i] != '\0')
if (isalnum(infix[i]))
postfix[j++] = infix[i];
else if (infix[i] == '(')
push(infix[i]);
else if (infix[i] == ')')
while ((x = pop()) != '(')
postfix[j++] = x;
else
while (priority(stack[top]) >= priority(infix[i]))
postfix[j++] = pop();
push(infix[i]);
}
i++;
while (top != -1)
postfix[j++] = pop();
postfix[j] = '\0';
// Evaluate postfix
int evalPostfix(char postfix[])
int i = 0;
int s[MAX];
int top2 = -1;
while (postfix[i] != '\0')
if (isdigit(postfix[i]))
s[++top2] = postfix[i] - '0';
else
{
int val1 = s[top2--];
int val2 = s[top2--];
switch (postfix[i])
case '+': s[++top2] = val2 + val1; break;
case '-': s[++top2] = val2 - val1; break;
case '*': s[++top2] = val2 * val1; break;
case '/': s[++top2] = val2 / val1; break;
case '^': s[++top2] = pow(val2, val1); break;
i++;
return s[top2];
int main()
char infix[MAX], postfix[MAX];
printf("Enter infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
int result = evalPostfix(postfix);
printf("Evaluation result: %d\n", result);
return 0;
}
Output
Run1
Enter infix expression: 2+3*4
Postfix expression: 234*+
Evaluation result: 14
Run2
Enter infix expression: (2+3)*(4+5)
Postfix expression: 23+45+*
Evaluation result: 45
2. Create a program to determine whether a given string is a
palindrome or not..
Palindrome Check Using Stack
Algorithm: Palindrome using Stack
1. Start
2. Read string
3. Push all characters into stack
4. For each character:
o Pop from stack
o Compare with original string
5. If all match Palindrome
6. Else Not palindrome
7. Stop
Program:
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Push operation
void push(char ch)
stack[++top] = ch;
// Pop operation
char pop()
return stack[top--];
int main()
char str[100];
int i, length, flag = 0;
printf("Enter a string: ");
scanf("%s", str);
length = strlen(str);
// Push all characters into stack
for (i = 0; i < length; i++)
push(str[i]);
// Compare with original string
for (i = 0; i < length; i++)
{
if (str[i] != pop())
flag = 1;
break;
if (flag == 0)
printf("The string is a Palindrome\n");
else
printf("The string is NOT a Palindrome\n");
return 0;
}
Sample Output
Enter a string: madam
The string is a Palindrome
Enter a string: hello
The string is NOT a Palindrome
3. Implement a queue to perform comparison and check for symmetry
To check symmetry (palindrome):
● Insert all characters into a queue
● Compare:
o Queue gives elements in forward order
o String from end gives reverse order
● If both match Symmetric (Palindrome)
Program (Using Queue)
#include <stdio.h>
#include <string.h>
#define MAX 100
char queue[MAX];
int front = 0, rear = -1;
// Enqueue
void enqueue(char ch)
queue[++rear] = ch;
// Dequeue
char dequeue()
return queue[front++];
int main()
char str[100];
int i, length, flag = 0;
printf("Enter a string: ");
scanf("%s", str);
length = strlen(str);
// Insert all characters into queue
for (i = 0; i < length; i++)
enqueue(str[i]);
// Compare queue with reverse string
for (i = length - 1; i >= 0; i--)
if (str[i] != dequeue())
flag = 1;
break;
if (flag == 0)
printf("The string is Symmetric (Palindrome)\n");
else
printf("The string is NOT Symmetric\n");
return 0;
}