Posted on by Kalkicode
Code Stack

# Reverse each word in a string

The problem is to reverse individual words in a given string. Given a sentence, we need to reverse each word in the sentence while maintaining the order of the words.

## Example

Let's say we have the following input string: "This is a simple words". After reversing individual words, the output should be "sihT si a elpmis sdrow".

## Idea to Solve the Problem

To reverse individual words in a string, we can use a stack to store characters of each word in the sentence. We iterate through the input string character by character and push each character into the stack until we encounter a space, which indicates the end of the current word. Once we encounter a space, we pop characters from the stack and append them to the result string, effectively reversing the word. We continue this process until we reach the end of the input string.

## Algorithm

1. Define a custom stack data structure with push, pop, is_empty, and peek operations.
2. Create a function `reversing_word` that takes the input string as input and returns the string with individual words reversed.
3. Initialize an empty result string to store the final output.
4. Iterate through the input string character by character.
5. If the character is not a space, push it into the stack.
6. If the character is a space or the end of the input string, it means we have reached the end of the current word. In this case:
• Pop characters from the stack and append them to the result string until the stack is empty. This will reverse the word.
• If it's not the end of the input string, append a space to the result string to separate the reversed words.
7. Continue the iteration until the end of the input string is reached.
8. Return the result string containing the individual words reversed.

## Pseudocode

``````FUNCTION reversing_word(text):
result = "" // Initialize an empty result string
stack = MyStack() // Create a new stack

FOR i = 0 to length of text - 1:
IF text[i] is not a space:
// Push non-space characters into the stack
stack.push(text[i])
ELSE:
// When a space is encountered, pop characters from stack
// and append them to the result string until the stack is empty
WHILE stack is not empty:
result += stack.peek()
stack.pop()
// If it's not the end of the input string, append a space to separate words
IF i is not length of text - 1:
result += " "

RETURN result
``````

## Code Solution

``````// Java program
// Reverse individual words of the sentence

//Stack Node
class Node
{
public char data;
public Node next;
public Node(char data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(char data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
System.out.print("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public char peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return ' ';
}
}
}
class ReverseStringWord
{
// Reverse the given string words
public String reversing_word(String text)
{
int size = text.length();
//Auxiliary variable which is used to store result of string
String result = "";
//Create an stack
MyStack stack = new MyStack();
for (int i = 0; i < size; i++)
{
if (text.charAt(i) == ' ')
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(text.charAt(i));
}
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
return result;
}
public static void main(String[] args)
{
ReverseStringWord obj = new ReverseStringWord();
String text = "This is a simple words";
System.out.print(" Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
System.out.print("\n After Reverse  : [" + text + "]");
text = "It's to good ";
System.out.print("\n Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
System.out.print("\n After Reverse  : [" + text + "]");
}
}``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````//Include header file
#include <iostream>
#include<string.h>

using namespace std;

// C++ program
// Reverse individual words of the sentence

//Stack Node
class Node
{
public:
char data;
Node *next;
Node(char data)
{
this->data = data;
this->next = NULL;
}
};
//Define custom stack and its operation
class MyStack
{
public:
Node *top;
MyStack()
{
this->top = NULL;
}
//Add a new element in stack
void push(char data)
{
//Make a new stack node
Node *new_node = new Node(data);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
else
{
cout << "Memory overflow\n";
}
}
//remove a top element in stack
void pop()
{
if (this->top != NULL)
{
this->top = this->top->next;
}
}
//check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
char peek()
{
if (this->top != NULL)
{
return this->top->data;
}
else
{
return ' ';
}
}
};
class ReverseStringWord
{
public:
// Reverse the given string words
string reversing_word(string text)
{
int size = text.size();
//Auxiliary variable which is used to store result of string
string result = "";
//Create an stack
MyStack stack = MyStack();
for (int i = 0; i < size; i++)
{
if (text[i] == ' ')
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(text[i]);
}
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
return result;
}
};
int main()
{
ReverseStringWord obj = ReverseStringWord();
string text = "This is a simple words";
cout << " Before Reverse : [" << text << "]";
text = obj.reversing_word(text);
cout << "\n After Reverse  : [" << text << "]";
text = "It's to good ";
cout << "\n Before Reverse : [" << text << "]";
text = obj.reversing_word(text);
cout << "\n After Reverse  : [" << text << "]";
return 0;
}``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````//Include namespace system
using System;

// C# program
// Reverse individual words of the sentence

//Stack Node
class Node
{
public char data;
public Node next;
public Node(char data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public Node top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(char data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
Console.Write("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public char peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return ' ';
}
}
}
class ReverseStringWord
{
// Reverse the given string words
public String reversing_word(String text)
{
int size = text.Length;
//Auxiliary variable which is used to store result of string
String result = "";
//Create an stack
MyStack stack = new MyStack();
for (int i = 0; i < size; i++)
{
if (text[i] == ' ')
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(text[i]);
}
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
return result;
}
public static void Main(String[] args)
{
ReverseStringWord obj = new ReverseStringWord();
String text = "This is a simple words";
Console.Write(" Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
Console.Write("\n After Reverse  : [" + text + "]");
text = "It's to good ";
Console.Write("\n Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
Console.Write("\n After Reverse  : [" + text + "]");
}
}``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````<?php
// Php program
// Reverse individual words of the sentence

//Stack Node
class Node
{
public \$data;
public \$next;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
}
}
//Define custom stack and its operation
class MyStack
{
public \$top;

function __construct()
{
\$this->top = null;
}
//Add a new element in stack
public	function push(\$data)
{
//Make a new stack node
\$new_node = new Node(\$data);
if (\$new_node != null)
{
\$new_node->next = \$this->top;
\$this->top = \$new_node;
}
else
{
echo "Memory overflow\n";
}
}
//remove a top element in stack
public	function pop()
{
if (\$this->top != null)
{
\$this->top = \$this->top->next;
}
}
//check that whether stack is empty or not
public	function is_empty()
{
if (\$this->top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public	function peek()
{
if (\$this->top != null)
{
return \$this->top->data;
}
else
{
return ' ';
}
}
}
class ReverseStringWord
{
// Reverse the given string words
public	function reversing_word(\$text)
{
\$size = strlen(\$text);
//Auxiliary variable which is used to store result of string
\$result = "";
//Create an stack
\$stack = new MyStack();
for (\$i = 0; \$i < \$size; \$i++)
{
if (\$text[\$i] == ' ')
{
// iterating the stack elements until if not empty
while (\$stack->is_empty() == false)
{
//Get top element
\$result .= \$stack->peek();
//remove current top
\$stack->pop();
}
\$result .= " ";
}
else
{
\$stack->push(\$text[\$i]);
}
}
// When last words are exist in stack
while (\$stack->is_empty() == false)
{
//Get top element
\$result .= \$stack->peek();
//remove current top
\$stack->pop();
}
return \$result;
}
}

function main()
{
\$obj = new ReverseStringWord();
\$text = "This is a simple words";
echo " Before Reverse : [". \$text ."]";
\$text = \$obj->reversing_word(\$text);
echo "\n After Reverse  : [". \$text ."]";
\$text = "It's to good ";
echo "\n Before Reverse : [". \$text ."]";
\$text = \$obj->reversing_word(\$text);
echo "\n After Reverse  : [". \$text ."]";
}
main();``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````// Node Js program
// Reverse individual words of the sentence

//Stack Node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
//Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
}
//Add a new element in stack
push(data)
{
//Make a new stack node
var new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
//remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return ' ';
}
}
}
class ReverseStringWord
{
// Reverse the given string words
reversing_word(text)
{
var size = text.length;
//Auxiliary variable which is used to store result of string
var result = "";
//Create an stack
var stack = new MyStack();
for (var i = 0; i < size; i++)
{
if (text[i] == ' ')
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(text[i]);
}
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
return result;
}
}

function main()
{
var obj = new ReverseStringWord();
var text = "This is a simple words";
process.stdout.write(" Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
process.stdout.write("\n After Reverse  : [" + text + "]");
text = "It's to good ";
process.stdout.write("\n Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
process.stdout.write("\n After Reverse  : [" + text + "]");
}
main();``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````#  Python 3 program
#  Reverse individual words of the sentence

# Stack Node
class Node :

def __init__(self, data) :
self.data = data
self.next = None

# Define custom stack and its operation
class MyStack :

def __init__(self) :
self.top = None

# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = Node(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")

# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next

# check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True

# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.data
else :
return ' '

class ReverseStringWord :
#  Reverse the given string words
def reversing_word(self, text) :
size = len(text)
# Auxiliary variable which is used to store result of string
result = ""
# Create an stack
stack = MyStack()
i = 0
while (i < size) :
if (text[i] == ' ') :
#  iterating the stack elements until if not empty
while (stack.is_empty() == False) :
# Get top element
result += stack.peek()
# remove current top
stack.pop()

result += " "
else :
stack.push(text[i])

i += 1

#  When last words are exist in stack
while (stack.is_empty() == False) :
# Get top element
result += stack.peek()
# remove current top
stack.pop()

return result

def main() :
obj = ReverseStringWord()
text = "This is a simple words"
print(" Before Reverse : [{0}]".format(text), end = "")
text = obj.reversing_word(text)
print("\n After Reverse  : [{0}]".format(text), end = "")
text = "It's to good "
print("\n Before Reverse : [{0}]".format(text), end = "")
text = obj.reversing_word(text)
print("\n After Reverse  : [{0}]".format(text), end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````#  Ruby program
#  Reverse individual words of the sentence

# Stack Node
class Node
# Define the accessor and reader of class Node
attr_accessor :data, :next

def initialize(data)
self.data = data
self.next = nil
end

end

# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top

def initialize()
self.top = nil
end

# Add a new element in stack
def push(data)
# Make a new stack node
new_node = Node.new(data)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
else
print("Memory overflow\n")
end

end

# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
end

end

# check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end

end

# Used to get top element of stack
def peek()
if (self.top != nil)
return self.top.data
else
return ' '
end

end

end

class ReverseStringWord
#  Reverse the given string words
def reversing_word(text)
size = text.length()
# Auxiliary variable which is used to store result of string
result = ""
# Create an stack
stack = MyStack.new()
i = 0
while (i < size)
if (text[i] == ' ')
#  iterating the stack elements until if not empty
while (stack.is_empty() == false)
# Get top element
result += stack.peek()
# remove current top
stack.pop()
end

result += " "
else
stack.push(text[i])
end

i += 1
end

#  When last words are exist in stack
while (stack.is_empty() == false)
# Get top element
result += stack.peek()
# remove current top
stack.pop()
end

return result
end

end

def main()
obj = ReverseStringWord.new()
text = "This is a simple words"
print(" Before Reverse : [", text ,"]")
text = obj.reversing_word(text)
print("\n After Reverse  : [", text ,"]")
text = "It's to good "
print("\n Before Reverse : [", text ,"]")
text = obj.reversing_word(text)
print("\n After Reverse  : [", text ,"]")
end

main()``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````// Scala program
// Reverse individual words of the sentence

//Stack Node
class Node(var data: Character,
var next: Node)
{
def this(data: Char)
{
this(data, null);
}
}
//Define custom stack and its operation
class MyStack(var top: Node)
{
def this()
{
this(null);
}
//Add a new element in stack
def push(data: Char): Unit = {
//Make a new stack node
var new_node: Node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
print("Memory overflow\n");
}
}
//remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
}
}
//check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
def peek(): Char = {
if (this.top != null)
{
return this.top.data;
}
else
{
return ' ';
}
}
}
class ReverseStringWord
{
// Reverse the given string words
def reversing_word(text: String): String = {
var size: Int = text.length();
//Auxiliary variable which is used to store result of string
var result: String = "";
//Create an stack
var stack: MyStack = new MyStack();
var i: Int = 0;
while (i < size)
{
if (text(i) == ' ')
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(text(i));
}
i += 1;
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += stack.peek();
//remove current top
stack.pop();
}
return result;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: ReverseStringWord = new ReverseStringWord();
var text: String = "This is a simple words";
print(" Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
print("\n After Reverse  : [" + text + "]");
text = "It's to good ";
print("\n Before Reverse : [" + text + "]");
text = obj.reversing_word(text);
print("\n After Reverse  : [" + text + "]");
}
}``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It's to good ]
After Reverse  : [s'tI ot doog ]``````
``````// Swift 4 program
// Reverse individual words of the sentence

//Stack Node
class Node
{
var data: Character;
var next: Node? ;
init(_ data: Character)
{
self.data = data;
self.next = nil;
}
}
//Define custom stack and its operation
class MyStack
{
var top: Node? ;
init()
{
self.top = nil;
}
//Add a new element in stack
func push(_ data: Character)
{
//Make a new stack node
let new_node: Node? = Node(data);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
//remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
}
}
//check that whether stack is empty or not
func is_empty() -> Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
func peek() -> Character
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return " ";
}
}
}
class ReverseStringWord
{
// Reverse the given string words
func reversing_word(_ text: String) -> String
{
let size: Int = text.count;
//Auxiliary variable which is used to store result of string
var result: String = "";
//Create an stack
let stack: MyStack = MyStack();
var i: Int = 0;
var data : Character;
while (i < size)
{
data = Array(text)[i];
if (data == " ")
{
// iterating the stack elements until if not empty
while (stack.is_empty() == false)
{
//Get top element
result +=  String(stack.peek());
//remove current top
stack.pop();
}
result += " ";
}
else
{
stack.push(data);
}
i += 1;
}
// When last words are exist in stack
while (stack.is_empty() == false)
{
//Get top element
result += String(stack.peek());
//remove current top
stack.pop();
}
return result;
}
}
func main()
{
let obj: ReverseStringWord = ReverseStringWord();
var text: String = "This is a simple words";
print(" Before Reverse : [\(text)]", terminator: "");
text = obj.reversing_word(text);
print("\n After Reverse  : [\(text)]", terminator: "");
text = "It\"s to good ";
print("\n Before Reverse : [\(text)]", terminator: "");
text = obj.reversing_word(text);
print("\n After Reverse  : [\(text)]", terminator: "");
}
main();``````

#### Output

`````` Before Reverse : [This is a simple words]
After Reverse  : [sihT si a elpmis sdrow]
Before Reverse : [It"s to good ]
After Reverse  : [s"tI ot doog ]``````

## Time Complexity Analysis

Let n be the length of the input string. The time complexity of the algorithm is O(n) because we iterate through the input string once and perform constant-time operations for each character (push, pop, append to the result string). Therefore, the overall time complexity is linear, O(n).

## Output Explanation

The output shows the original string and the string with individual words reversed. For example, "Before Reverse : [This is a simple words]" and "After Reverse : [sihT si a elpmis sdrow]" represent the input string "This is a simple words" and the output string after reversing individual words, respectively.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post