Depth-First Search (DFS) in 2D Matrix/2D-Array – Iterative Solution

Objective: Given a two-dimensional array or matrix, Do the depth-First Search (DFS) to print the elements of the given matrix. Implement the Depth-first traversal in an iterative manner. Example: int [][] grid = new int[][] { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} Output: Depth-First Traversal: … Read more Depth-First Search (DFS) in 2D Matrix/2D-Array – Iterative Solution

Print Stack in reverse order.

Objective: Given a stack, write a program to print the stack elements in reverse order. Example: Approach: Use Temporary stack: Take temporary stack, and copy all the items from the given stack to a temporary stack. Elements will be stored in a temporary stack in reverse order. Now print elements from the temporary stack and … Read more Print Stack in reverse order.

Sort a given stack – Using Recursion

Objective: Given a stack of integers, write an algorithm to sort the stack using recursion.  Example: Original Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Original Stack: [4, 9, 6, 8, 10, 5] Sorted Stack is:[10, 9, 8, 6, 5, 4]  Approach: In this solution, we need two … Read more Sort a given stack – Using Recursion

Evaluation of Prefix Expressions (Polish Notation) | Set 2

Earlier we had discussed how to evaluate prefix expression where operands are of single-digit. In this article, we will discuss how to evaluate prefix expression for any number ( not necessarily single digit.) Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. Let’s assume the below Operands … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 2

Evaluation of Prefix Expressions (Polish Notation) | Set 1

Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. There are no precedence rules to learn. Let’s assume the below Operands are real numbers in real digits. (Later we will Enhance the solution for any number) Permitted operators: +,-, *, /, ^(exponentiation) Blanks are NOT permitted in … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 1

Smallest Number after Removing K digits

Objective: Given a number with N digits, write a program to get the smallest number possible after removing k digits from number N. OR Implement a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. Example: N = 1453287, k = 3 Output: 1287 … Read more Smallest Number after Removing K digits

Reverse a Stack using recursion – In Place (Without using extra memory)

Objective: Given a Stack, write an algorithm to reverse the stack. Example: Original Stack: [14, 9, 67, 91, 101, 25] Reversed Stack: [25, 101, 91, 67, 9, 14] Approach: Use Recursion In this solution, we need two recursive functions. reverse() and insert_at_bottom(). reverse() – this function will be called by the driver. In this function, … Read more Reverse a Stack using recursion – In Place (Without using extra memory)

Convert Prefix to Postfix Expression

Objective: Given a Prefix expression, write an algorithm to convert it into Postfix expression. Example: Input: Prefix expression:  + A B  Output: Postfix expression: A B + Input: Prefix expression:  *-A/BC-/AKL Output: Postfix expression: ABC/-AK/L-* Approach: Use Stacks Algorithm: Iterate the given expression from right to left, one character at a time If the character … Read more Convert Prefix to Postfix Expression

Sort a given stack – Using Temporary Stack

Objective: Given a stack of integers, write an algorithm to sort the stack using a temporary stack.  Example: Given Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Approach: Use another stack, let’s call it a temporary stack. While given original is not empty Pop the element from the … Read more Sort a given stack – Using Temporary Stack

Convert Postfix to Infix Expression

Objective: Given a Postfix expression, write an algorithm to convert it into Infix expression. Example: Input: Postfix expression:  A B +  Output: Infix expression- (A + B) Input: Postfix expression:  ABC/-AK/L-* Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stack Algorithm: Iterate the given expression from left to right, one character at a time If a character … Read more Convert Postfix to Infix Expression

Convert Prefix to Infix Expression

Objective: Given a Prefix expression, write an algorithm to convert it into Infix expression. Example: Input: Prefix expression: + A B Output: Infix expression- (A + B) Input: Prefix expression: *-A/BC-/AKL Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stacks Algorithm: Iterate the given expression from right to left (in reverse order), one character at a time … Read more Convert Prefix to Infix Expression

Convert Infix to Prefix Expression

Objective: Given an Infix expression, write an algorithm to convert it into Prefix expression. Example: Input: Infix expression – A + B Output: Prefix expression- +AB Input: Infix expression – A+B*(C^D-E) Output: Prefix expression- +A*B-^CDE Approach: Use Stack Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Prefix Expression

Convert Infix to Postfix Expression

Objective: Given an Infix expression, write an algorithm to convert it into Postfix expression. Example: Input: Infix expression – A + B Output: Postfix expression- AB+ Input: Infix expression – A+B*(C^D-E) Output: Postfix expression- ABCD^E-*+ Approach: Use Stacks Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Postfix Expression

Evaluation of Infix expressions

Infix notation is commonly used in arithmetic formula or statements, the operators are written in-between their operands. Let’s assume the below Operands are real numbers. Permitted operators: +,-, *, /, ^(exponentiation) Blanks are permitted in expression. Parenthesis are permitted Example: A * ( B + C ) / D 2 * (5 + 3) / … Read more Evaluation of Infix expressions

Stack Java Class – Explained

Earlier we saw about Stack and its implementation using Linked List. Java has a built in class for Stack. In this article we will discuss about it in detail. First brief about Stack. What is Stack?? Stack is an abstract data type (ADT) and very useful in programming. In computer science, a stack is an abstract data type that serves … Read more Stack Java Class – Explained