Data Structure and Algorithms

[Link]

Stack

A stack is a list of elements in which an element may be inserted or

deleted only at one end, called the top of the stack. Stacks are sometimes
known as LIFO (last in, first out) lists.
As the items can be added or removed only from the top i.e. the last item
to be added to a stack is the first item to be removed.

The two basic operations associated with stacks are:

• Push: is the term used to insert an element into a stack.

• Pop: is the term used to delete an element from a stack.

“Push” is the term used to insert an element into a stack. “Pop” is the
term used to delete an element from the stack.

All insertions and deletions take place at the same end, so the last element
added to the stack will be the first element removed from the stack. When
a stack is created, the stack base remains fixed while the stack top
changes as elements are added and removed. The most accessible
element is the top and the least accessible element is the bottom of the
stack.

➔Representation of Stack:

Let us consider a stack with 6 elements capacity. This is called as the size
of the stack. The number of elements to be added should not exceed the
maximum size of the stack. If we attempt to add new element beyond the
maximum size, we will encounter a stack overflow condition. Similarly,
you cannot remove elements beyond the base of the stack. If such is the
case, we will reach a stack underflow condition.

When an element is added to a stack, the operation is performed by

push(). Figure 1 shows the creation of a stack and addition of elements
using push().

©Topperworld
Data Structure and Algorithms

4 4 4 4

3 3 3 3
TOP
2 2 2 33 2
TOP
22 22
1 TOP 1 1 1
11 11 11
TOP 0 0 0 0
Empty Insert Insert Insert
Stack 11 22 33

Figure 1. Push operations on stack

When an element is taken off from the stack, the operation is performed
by pop(). Figure 2 shows a stack initially with three elements and shows
the deletion of elements using pop().

4 4 4 4

TOP 3 3 3 3
33 2 2 2 2
TOP
22 22
1 1 TOP 1 1
11 11 11 TOP
0 0 0 0
Initial POP POP POP
Stack
Empty
Stack
Figure 2. Pop operations on stack

Source code for stack operations, using array:

class Stack {
private int maxSize;
private int[] stackArray;
private int top;

public Stack(int size) {

maxSize = size;
stackArray = new int[maxSize];
top = -1;
}

public boolean isEmpty() {

return top == -1;
}

©Topperworld
Data Structure and Algorithms

public boolean isFull() {

return top == maxSize - 1;
}

public void push(int data) {

if (isFull()) {
[Link]("Stack is full. Cannot push " +
data);
return;
}
stackArray[++top] = data;
}

public int pop() {

if (isEmpty()) {
[Link]("Stack is empty. Cannot pop.");
return -1;
}
return stackArray[top--];
}

public int peek() {

if (isEmpty()) {
[Link]("Stack is empty. Cannot peek.");
return -1;
}
return stackArray[top];
}

public void display() {

if (isEmpty()) {
[Link]("Stack is empty.");
return;
}
[Link]("Stack: ");
for (int i = 0; i <= top; i++) {
[Link](stackArray[i] + " ");
}
[Link]();
}
}

©Topperworld
Data Structure and Algorithms

public class StackExample {

public static void main(String[] args) {
Stack stack = new Stack(5);

[Link](1);
[Link](2);
[Link](3);

[Link]();

int poppedItem = [Link]();

[Link]("Popped: " + poppedItem);

[Link](4);
[Link](5);

[Link]();

int peekedItem = [Link]();

[Link]("Peeked: " + peekedItem);
}
}

OUTPUT:-

Stack: 1 2 3
Popped: 3
Stack: 1 2 4 5
Peeked: 5

©Topperworld
Data Structure and Algorithms

➔Linked List Implementation of Stack:

We can represent a stack as a linked list. In a stack push and pop

operations are performed at one end called top. We can perform similar
operations at one end of list using top pointer. The linked stack looks as
shown in figure 3.

top
400
data next
40 X
400

30 400
300

20 300
200
start
100 10 200
100

Figure 3. Linked stack

representation

Source code for stack operations, using linked list:

class Node {
int data;
Node next;

public Node(int data) {

[Link] = data;
[Link] = null;
}
}

class Stack {
private Node top;

public boolean isEmpty() {

return top == null;
}

©Topperworld
Data Structure and Algorithms

public void push(int data) {

Node newNode = new Node(data);
[Link] = top;
top = newNode;
}

public int pop() {

if (isEmpty()) {
[Link]("Stack is empty. Cannot pop.");
return -1;
}
int poppedItem = [Link];
top = [Link];
return poppedItem;
}

public int peek() {

if (isEmpty()) {
[Link]("Stack is empty. Cannot peek.");
return -1;
}
return [Link];
}

public void display() {

if (isEmpty()) {
[Link]("Stack is empty.");
return;
}
[Link]("Stack: ");
Node current = top;
while (current != null) {
[Link]([Link] + " ");
current = [Link];
}
[Link]();
}
}

public class StackLinkedListExample {

public static void main(String[] args) {

©Topperworld
Data Structure and Algorithms

Stack stack = new Stack();

[Link](1);
[Link](2);
[Link](3);

[Link]();

int poppedItem = [Link]();

[Link]("Popped: " + poppedItem);

[Link](4);
[Link](5);

[Link]();

int peekedItem = [Link]();

[Link]("Peeked: " + peekedItem);
}
}

OUTPUT:-

Stack: 3 2 1
Popped: 3
Stack: 5 4 2 1
Peeked: 5

➔Algebraic Expressions:

An algebraic expression is a legal combination of operators and operands.

Operand is the quantity on which a mathematical operation is performed.
Operand may be a variable like x, y, z or a constant like 5, 4, 6 etc.
Operator is a symbol which signifies a mathematical or logical operation
between the operands. Examples of familiar operators include +, -, *, /,
^ etc.

An algebraic expression can be represented using three different

notations. They are infix, postfix and prefix notations:

©Topperworld
Data Structure and Algorithms

Infix: It is the form of an arithmetic expression in which we fix (place)

the arithmetic operator in between the two operands.

Example: (A + B) * (C - D)

Prefix: It is the form of an arithmetic notation in which we fix (place)

the arithmetic operator before (pre) its two operands. The
prefix notation is called as
polish notation (due to the polish mathematician Jan
Lukasiewicz in the year 1920).

Example: * + A B – C D

Postfix: It is the form of an arithmetic expression in which we fix (place)

the arithmetic operator after (post) its two operands. The
postfix notation is called as suffix notation and is also referred
to reverse polish notation.

Example: A B + C D - *

The three important features of postfix expression are:

1. The operands maintain the same order as in the equivalent infix

expression.

2. The parentheses are not needed to designate the expression

unambiguously.

3. While evaluating the postfix expression the priority of the

operators is no longer relevant.

We consider five binary operations: +, -, *, / and $ or ↑ (exponentiation).

For these binary operations, the following in the order of precedence
(highest to lowest):

OPERATOR PRECEDENCE VALUE

Exponentiation ($ Highest 3
or ↑ or ^)
*, / Next highest 2
+, - Lowest 1

©Topperworld
Data Structure and Algorithms

Converting expressions using Stack:

Let us convert the expressions from one type to another. These can be
done as follows:

1. Infix to postfix
2. Infix to prefix
3. Postfix to infix
4. Postfix to prefix
5. Prefix to infix
6. Prefix to postfix

Conversion from infix to postfix:

Procedure to convert from infix expression to postfix expression is as

follows:

1. Scan the infix expression from left to right.

2. a) If the scanned symbol is left parenthesis, push it onto the

stack.

b) If the scanned symbol is an operand, then place directly in

the postfix expression (output).

c) If the symbol scanned is a right parenthesis, then go on

popping all the items from the stack and place them in the
postfix expression till we get the matching left parenthesis.

d) If the scanned symbol is an operator, then go on removing

all the operators from the stack and place them in the
postfix expression, if and only if the precedence of the
operator which is on the top of the stack is greater than (or
greater than or equal) to the precedence of the scanned
operator and push the scanned operator onto the stack
otherwise, push the scanned operator onto the stack.

©Topperworld
Data Structure and Algorithms

Example 1:

Convert ((A – (B + C)) * D) ↑ (E + F) infix expression to postfix form:

SYMBOL POSTFIX STRING STACK REMARKS

( (
( ( (
A A ( (
- A ( ( -
( A ( ( - (
B A B ( ( - (
+ A B ( ( - (+
C A B C ( ( - (+
) A B C + ( ( -
) A B C + - (
* A B C + - ( *
D A B C + - D ( *
) A B C + - D *
↑ A B C + - D * ↑
( A B C + - D
↑( *
E A B C + E - D
↑( *
+ A B C + E - D
↑(+ *
F A B C + EF- D
↑(+ *
) A B C + -
EF+ ↑ D *
End of The input is now empty. Pop the output
string A B C + - D * E F + symbols from the stack until it is empty.
↑

Example 2:

Convert a + b * c + (d * e + f) * g the infix expression into postfix form.

SYMBOL POSTFIX STRING STACK REMARKS

a a
+ a +
b ab +
* ab +*
c abc +*

©Topperworld
Data Structure and Algorithms

+ abc*+ +
( abc*+ +(
d abc*+d +(
* abc*+d +(*
e abc*+de +(*
+ abc*+de* +(+
f abc*+de*f +(+
) abc*+de*f+ +
* abc*+de*f+ +*
g abc*+de*f+ +*
g
End of a b c * + d e * f + The input is now empty. Pop the output
string g*+ symbols from the stack until it is empty.

Example 3:

Convert the following infix expression A + B * C – D / E * H into its

equivalent postfix expression.

SYMBOL POSTFIX STRING STACK REMARKS

A A
+ A +
B AB +
* AB +*
C ABC +*
- ABC*+ -
D ABC*+D -
/ ABC*+D -/
E ABC*+DE -/
* ABC*+DE/ -*
H ABC*+DE/H -*
End of The input is now empty. Pop the output
string ABC*+DE/H symbols from the stack until it is empty.
*-

©Topperworld
Data Structure and Algorithms

Example 4:

Convert the following infix expression A + (B * C – (D / E ↑ F) * G) * H

into its equivalent postfix expression.

SYMBOL POSTFIX STRING STACK REMARKS

A A
+ A +
( A +(
B A B + (
* A B + ( *
C A B C + ( *
- A B C * + ( -
( A B C * + ( -(
D A B C * D + ( -(
/ A B C * D + ( -(/
E A B C * DE + ( -(/
↑ A B C * DE + ( -(/
↑
F ABC*DEF +(-(/
↑
) AB C * D E F ↑ / +(-
* AB C * D E F ↑ / +(-*
G AB C * D E F ↑ /G +(-*
) AB C * D E F ↑ /G* +
-
* AB C*DEF ↑ /G* +*
-
H AB C*DEF ↑ /G* +*
-H
End of The input is now empty. Pop the
ABC*DEF ↑ /G*
string output symbols from the stack until
-H*+
it is empty.

©Topperworld
Data Structure and Algorithms

Program to convert an infix to postfix expression:

import [Link];

public class InfixToPostfix {

public static String infixToPostfix(String infix) {
StringBuilder postfix = new StringBuilder();
Stack<Character> stack = new Stack<>();

for (char c : [Link]()) {

if ([Link](c)) {
[Link](c);
} else if (c == '(') {
[Link](c);
} else if (c == ')') {
while (![Link]() && [Link]() != '(')
{
[Link]([Link]());
}
if (![Link]() && [Link]() != '(') {
return "Invalid Expression"; // Unmatched
parenthesis
} else {
[Link](); // Pop '('
}
} else {
while (![Link]() && precedence(c) <=
precedence([Link]())) {
[Link]([Link]());
}
[Link](c);
}
}

while (![Link]()) {
if ([Link]() == '(') {
return "Invalid Expression"; // Unmatched
parenthesis
}
[Link]([Link]());
}

©Topperworld
Data Structure and Algorithms

return [Link]();
}

public static int evaluatePostfix(String postfix) {

Stack<Integer> stack = new Stack<>();

for (char c : [Link]()) {

if ([Link](c)) {
[Link](c - '0');
} else {
int operand2 = [Link]();
int operand1 = [Link]();
int result;
switch (c) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
default:
throw new
IllegalArgumentException("Invalid operator: " + c);
}
[Link](result);
}
}

return [Link]();
}

private static int precedence(char operator) {

switch (operator) {
case '+':
case '-':
return 1;

©Topperworld
Data Structure and Algorithms

case '*':
case '/':
return 2;
}
return -1;
}

public static void main(String[] args) {

String infixExpression = "3+5*(2-6)/2";
String postfixExpression =
infixToPostfix(infixExpression);

[Link]("Infix Expression: " +

infixExpression);
[Link]("Postfix Expression: " +
postfixExpression);

int result = evaluatePostfix(postfixExpression);

[Link]("Result: " + result);
}
}

OUTPUT:-

Infix Expression: 3+5*(2-6)/2

Postfix Expression: 3526-2/*+
Result: -7

➔Conversion from infix to prefix:

The precedence rules for converting an expression from infix to prefix are
identical. The only change from postfix conversion is that traverse the
expression from right to left and the operator is placed before the
operands rather than after them. The prefix form of a complex expression
is not the mirror image of the postfix form.

Example 1:

Convert the infix expression A + B - C into prefix expression.

PREFIX
SYMBOL STACK REMARKS
STRING

©Topperworld
Data Structure and Algorithms

C C
- C -
B BC -
+ BC -+
A ABC -+
End of - + A B C The input is now empty. Pop the output symbols
string from the stack until it is empty.

Example 2:

Convert the infix expression (A + B) * (C - D) into prefix expression.

PREFIX
SYMBOL STACK REMARKS
STRING
) )
D D )
- D )-
C CD )-
( -CD
* -CD *
) -CD *)
B B-CD *)
+ B-CD *)+
A AB-CD *)+
( +AB–C *
D
End of * + A B – The input is now empty. Pop the output symbols
string C D from the stack until it is empty.

Example 3:

Convert the infix expression A ↑ B * C – D + E / F / (G + H) into prefix

expression.

SYMBOL PREFIX STRING STACK REMARKS

) )
H H )

©Topperworld
Data Structure and Algorithms

+ H )+
G GH )+
( +GH
/ +GH /
F F+GH /
/ F+GH //
E EF+GH //
+ //EF+GH +
D D//EF+GH +
- D//EF+GH +-
C CD//EF+GH +-
* CD//EF+GH +-*
B BCD//EF+GH +-*
↑ BCD//EF+GH +-*↑
A ABCD//EF+GH +-*↑
End of The input is now empty. Pop the
+-* ↑ ABCD//EF+
string output symbols from the stack
GH
until it is empty.

Program to convert an infix to prefix expression:

import [Link];

public class InfixToPrefix {

public static String infixToPrefix(String infix) {
StringBuilder prefix = new StringBuilder();
StringBuilder reverseInfix = new
StringBuilder(infix).reverse();
Stack<Character> stack = new Stack<>();

for (char c : [Link]().toCharArray()) {

if ([Link](c)) {
[Link](c);
} else if (c == ')') {
[Link](c);
} else if (c == '(') {
while (![Link]() && [Link]() != ')')
{

©Topperworld
Data Structure and Algorithms

[Link]([Link]());
}
if (![Link]() && [Link]() != ')') {
return "Invalid Expression"; // Unmatched
parenthesis
} else {
[Link](); // Pop ')'
}
} else {
while (![Link]() && precedence(c) <
precedence([Link]())) {
[Link]([Link]());
}
[Link](c);
}
}

while (![Link]()) {
if ([Link]() == ')') {
return "Invalid Expression"; // Unmatched
parenthesis
}
[Link]([Link]());
}

return [Link]().toString();
}

public static int evaluatePrefix(String prefix) {

StringBuilder reversePrefix = new
StringBuilder(prefix).reverse();
Stack<Integer> stack = new Stack<>();

for (char c : [Link]().toCharArray()) {

if ([Link](c)) {
[Link](c - '0');
} else {
int operand1 = [Link]();
int operand2 = [Link]();
int result;
switch (c) {
case '+':

©Topperworld
Data Structure and Algorithms

result = operand1 + operand2;

break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
default:
throw new
IllegalArgumentException("Invalid operator: " + c);
}
[Link](result);
}
}

return [Link]();
}

private static int precedence(char operator) {

switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}

public static void main(String[] args) {

String infixExpression = "3+5*(2-6)/2";
String prefixExpression =
infixToPrefix(infixExpression);

[Link]("Infix Expression: " +

infixExpression);

©Topperworld
Data Structure and Algorithms

[Link]("Prefix Expression: " +

prefixExpression);

int result = evaluatePrefix(prefixExpression);

[Link]("Result: " + result);
}
}

OUTPUT:-

Infix Expression: 3+5*(2-6)/2

Prefix Expression: +3/*-5262
Result: -7

➔Conversion from postfix to infix:

Procedure to convert postfix expression to infix expression is as follows:

1. Scan the postfix expression from left to right.

2. If the scanned symbol is an operand, then push it onto the

stack.

3. If the scanned symbol is an operator, pop two symbols from

the stack and create it as a string by placing the operator in
between the operands and push it onto the stack.

4. Repeat steps 2 and 3 till the end of the expression.

Example:

Convert the following postfix expression A B C * D E F ^ / G * - H * + into

its equivalent infix expression.

©Topperworld
Data Structure and Algorithms

Program to convert postfix to infix expression:

import [Link];

public class PostfixToInfix {

public static String postfixToInfix(String postfix) {
Stack<String> stack = new Stack<>();

for (char c : [Link]()) {

if ([Link](c)) {
[Link]([Link](c));
} else {
String operand2 = [Link]();
String operand1 = [Link]();

©Topperworld
Data Structure and Algorithms

String result = "(" + operand1 + c + operand2 +

")";
[Link](result);
}
}

if ([Link]() != 1) {
return "Invalid Postfix Expression";
}

return [Link]();
}

public static void main(String[] args) {

String postfixExpression = "345*+2/";
String infixExpression =
postfixToInfix(postfixExpression);

[Link]("Postfix Expression: " +

postfixExpression);
[Link]("Infix Expression: " +
infixExpression);
}
}

OUTPUT:-

Postfix Expression: 345*+2/

Infix Expression: ((3+4)*5)/2

➔Conversion from postfix to prefix:

Procedure to convert postfix expression to prefix expression is as follows:

1. Scan the postfix expression from left to right.

2. If the scanned symbol is an operand, then push it onto the

stack.

©Topperworld
Data Structure and Algorithms

3. If the scanned symbol is an operator, pop two symbols from

the stack and create it as a string by placing the operator in
front of the operands and push it onto the stack.

5. Repeat steps 2 and 3 till the end of the expression.

Example:

Convert the following postfix expression A B C * D E F ^ / G * - H * + into

its equivalent prefix expression.

©Topperworld
Data Structure and Algorithms

Program to convert postfix to prefix expression:

import [Link];

public class PostfixToPrefix {

public static String postfixToPrefix(String postfix) {
Stack<String> stack = new Stack<>();

for (char c : [Link]()) {

if ([Link](c)) {
[Link]([Link](c));
} else {
String operand2 = [Link]();
String operand1 = [Link]();
String result = c + operand1 + operand2;
[Link](result);
}
}

if ([Link]() != 1) {
return "Invalid Postfix Expression";
}

return [Link]();
}

public static void main(String[] args) {

String postfixExpression = "34*5+2/";
String prefixExpression =
postfixToPrefix(postfixExpression);

[Link]("Postfix Expression: " +

postfixExpression);
[Link]("Prefix Expression: " +
prefixExpression);
}
}

©Topperworld
Data Structure and Algorithms

OUTPUT:-

Postfix Expression: 34*5+2/

Prefix Expression: +*3452

➔Conversion from prefix to infix:

Procedure to convert prefix expression to infix expression is as follows:

1. Scan the prefix expression from right to left (reverse order).

2. If the scanned symbol is an operand, then push it onto the
stack.
3. If the scanned symbol is an operator, pop two symbols from
the stack and create it as a string by placing the operator in
between the operands and push it onto the stack.

4. Repeat steps 2 and 3 till the end of the expression.

Example:

Convert the following prefix expression + A * - * B C * / D ^ E F G H into

its equivalent infix expression.

©Topperworld
Data Structure and Algorithms

Program to convert prefix to infix expression:

import [Link];

public class PrefixToInfix {

public static String prefixToInfix(String prefix) {
Stack<String> stack = new Stack<>();

for (int i = [Link]() - 1; i >= 0; i--) {

char c = [Link](i);
if ([Link](c)) {
[Link]([Link](c));
} else {
String operand1 = [Link]();
String operand2 = [Link]();
String result = "(" + operand1 + c + operand2 +
")";
[Link](result);
}
}

if ([Link]() != 1) {
return "Invalid Prefix Expression";
}

return [Link]();
}

public static void main(String[] args) {

String prefixExpression = "+*3452";

©Topperworld
Data Structure and Algorithms

String infixExpression =
prefixToInfix(prefixExpression);

[Link]("Prefix Expression: " +

prefixExpression);
[Link]("Infix Expression: " +
infixExpression);
}
}

OUTPUT:-

Prefix Expression: +*3452

Infix Expression: ((3*4)+5)/2

➔Conversion from prefix to postfix:

Procedure to convert prefix expression to postfix expression is as follows:

1. Scan the prefix expression from right to left (reverse order).

2. If the scanned symbol is an operand, then push it onto the

stack.

3. If the scanned symbol is an operator, pop two symbols from

the stack and create it as a string by placing the operator after
the operands and push it onto the stack.

4. Repeat steps 2 and 3 till the end of the expression.

©Topperworld
Data Structure and Algorithms

Example:

Convert the following prefix expression + A * - * B C * / D ^ E F G H into

its equivalent postfix expression.

©Topperworld
Data Structure and Algorithms

Program to convert prefix to postfix expression:

import [Link];

public class PrefixToPostfix {

public static String prefixToPostfix(String prefix) {
Stack<String> stack = new Stack<>();

for (int i = [Link]() - 1; i >= 0; i--) {

char c = [Link](i);
if ([Link](c)) {
[Link]([Link](c));
} else {
String operand1 = [Link]();
String operand2 = [Link]();
String result = operand1 + operand2 + c;
[Link](result);
}
}

if ([Link]() != 1) {
return "Invalid Prefix Expression";
}

return [Link]();
}

public static void main(String[] args) {

String prefixExpression = "+*3452";
String postfixExpression =
prefixToPostfix(prefixExpression);

[Link]("Prefix Expression: " +

prefixExpression);
[Link]("Postfix Expression: " +
postfixExpression);
}
}

©Topperworld
 Data Structure and Algorithms

OUTPUT:-

Prefix Expression: +*3452

Postfix Expression: 34*5+2+

Evaluation of postfix expression:

The postfix expression is evaluated easily by the use of a stack. When a

number is seen, it is pushed onto the stack; when an operator is seen, the
operator is applied to the two numbers that are popped from the stack and
the result is pushed onto the stack. When an expression is given in postfix
notation, there is no need to know any precedence rules; this is our
obvious advantage.

Example 1:

Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *

OPERAND OPERAND
SYMBOL VALUE STACK REMARKS
1 2
6 6
5 6, 5
2 6, 5, 2
The first four symbols
3 6, 5, 2, 3
are placed on the stack.
Next a ‘+’ is read, so 3
and 2 are popped from
+ 2 3 5 6, 5, 5
the stack and their sum
5, is pushed
8 2 3 5 6, 5, 5, 8 Next 8 is pushed
Now a ‘*’ is seen, so 8 and
* 5 8 40 6, 5, 40 5 are popped as 8 * 5 =
40 is pushed
Next, a ‘+’ is seen, so 40
+ 5 40 45 6, 45 and 5 are popped and 40
+ 5 = 45 is pushed
3 5 40 45 6, 45, 3 Now, 3 is pushed
Next, ‘+’ pops 3 and 45
+ 45 3 48 6, 48 and pushes 45 + 3 = 48
is pushed

©Topperworld
Data Structure and Algorithms

Finally, a ‘*’ is seen and

48 and 6 are popped, the
* 6 48 288 288
result 6 * 48 = 288 is
pushed

Example 2:

Evaluate the following postfix expression: 6 2 3 + - 3 8 2 / + * 2 ↑ 3+

SYMBOL OPERAND OPERAND VALUE STACK

1 2
6 6
2 6, 2
3 6, 2,
3
+ 2 3 5 6, 5
- 6 5 1 1
3 6 5 1 1, 3
8 6 5 1 1, 3,
8
2 6 5 1 1, 3,
8, 2
/ 8 2 4 1, 3,
4
+ 3 4 7 1, 7
* 1 7 7 7
2 1 7 7 7, 2
↑ 7 2 49 49
3 7 2 49 49, 3
+ 49 3 52 52

©Topperworld
Data Structure and Algorithms

Program to evaluate a postfix expression:

import [Link];

public class EvaluatePostfix {

public static int evaluatePostfix(String postfix) {
Stack<Integer> stack = new Stack<>();

for (char c : [Link]()) {

if ([Link](c)) {
[Link](c - '0');
} else {
int operand2 = [Link]();
int operand1 = [Link]();
int result;
switch (c) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
if (operand2 == 0) {
throw new ArithmeticException("Division
by zero");
}
result = operand1 / operand2;
break;
default:
throw new IllegalArgumentException("Invalid
operator: " + c);
}
[Link](result);
}
}

if ([Link]() != 1) {
throw new IllegalArgumentException("Invalid Postfix
Expression");
}

return [Link]();
}

©Topperworld
Data Structure and Algorithms

public static void main(String[] args) {

String postfixExpression = "34*5+2/";
int result = evaluatePostfix(postfixExpression);

[Link]("Postfix Expression: " +

postfixExpression);
[Link]("Result: " + result);
}
}

OUTPUT:-

Postfix Expression: 34*5+2/

Result: -7

➔Applications of stacks:

1. Stack is used by compilers to check for balancing of parentheses,

brackets and braces.

2. Stack is used to evaluate a postfix expression.

3. Stack is used to convert an infix expression into postfix/prefix

form.

4. In recursion, all intermediate arguments and return values are

stored on the processor’s stack.

5. During a function call the return address and arguments are

pushed onto a stack and on return they are popped off.

©Topperworld