Infix to prefix conversion

Here given code implementation process.

// Java program
// infix to prefix conversion
//Stack Node
class Node
{
	public String data;
	public Node next;
	public Node(String data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyStack
{
	public Node top;
	public MyStack()
	{
		this.top = null;
	}
	//Check two operands exist or not
	public boolean is_two_operands()
	{
		int counter = 0;
		Node temp = this.top;
		while (temp != null && counter < 2)
		{
			counter++;
			temp = temp.next;
		}
		return counter == 2;
	}
	//Add a new element in stack
	public void push(String data)
	{
		//Make a new stack node
		Node new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = top;
			top = new_node;
		}
		else
		{
			System.out.print("Memory overflow\n");
		}
	}
	//Add a top element in stack
	public String pop()
	{
		String temp = "";
		if (top != null)
		{
			temp = top.data;
			top = top.next;
		}
		return temp;
	}
	public boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public String peek()
	{
		if (top != null)
		{
			return top.data;
		}
		else
		{
			return "";
		}
	}
	public int precedence(String text)
	{
		if (text.equals("+") || text.equals("-"))
		{
			return 1;
		}
		else if (text.equals("*") || text.equals("/"))
		{
			return 2;
		}
		else if (text.equals("^"))
		{
			return 3;
		}
		return -1;
	}
	public boolean is_operator(char text)
	{
		if (text == '+' 
            || text == '-' 
            || text == '*' 
            || text == '/' 
            || text == '^')
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	public void prefix_conversion(String infix)
	{
		//Get the size
		int size = infix.length();
		//Create stack object
		MyStack collection = new MyStack();
		MyStack op = new MyStack();
		//Some useful variables which is using of to storing current result
		String auxiliary = "";
		String op1 = "";
		String op2 = "";
		boolean is_valid = true;
		for (int i = 0; i < size && is_valid; i++)
		{
			if (infix.charAt(i) == '(')
			{
				op.push("(");
			}
			else if (is_operator(infix.charAt(i)))
			{
				//When get a operator 
				while (collection.is_two_operands() && precedence("" + infix.charAt(i)) <= precedence(op.peek()))
				{
					op1 = collection.pop();
					op2 = collection.pop();
					auxiliary = op.pop() + op2 + op1;
					//Add new result into stack
					collection.push(auxiliary);
				}
				auxiliary = "" + infix.charAt(i);
				op.push(auxiliary);
			}
			else if (infix.charAt(i) == ')')
			{
				if (collection.is_two_operands())
				{
					while (collection.is_two_operands() && !op.peek().equals("("))
					{
						op1 = collection.pop();
						op2 = collection.pop();
						auxiliary = op.pop() + op2 + op1;
						//Add new result into stack
						collection.push(auxiliary);
					}
					op.pop();
				}
				else
				{
					is_valid = false;
				}
			}
			else if ((infix.charAt(i) >= '0' 
                      && infix.charAt(i) <= '9') 
                     || (infix.charAt(i) >= 'a' 
                         && infix.charAt(i) <= 'z') 
                     || (infix.charAt(i) >= 'A' 
                         && infix.charAt(i) <= 'Z'))
			{
				auxiliary = "" + infix.charAt(i);
				collection.push(auxiliary);
			}
			else
			{
				is_valid = false;
			}
		}
		if (is_valid == false)
		{
			System.out.print("Invalid infix : " + infix);
		}
		else
		{
			System.out.print("\n Infix   : " + infix);
			System.out.print("\n Prefix  : " + collection.pop());
		}
	}
	public static void main(String[] args)
	{
		MyStack obj = new MyStack();
		String infix = "((a*b)+(c^d))";
		obj.prefix_conversion(infix);
		infix = "((a/(b-c+d))*(e-a)*c)";
		obj.prefix_conversion(infix);
	}
}

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
//Include header file
#include <iostream>
#include <string.h>
using namespace std;

// C++ program
// infix to prefix conversion
//Stack Node
class Node
{
    public: 
    string data;
    Node * next;
    Node(string data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class MyStack
{
    public: 
    Node * top;
    MyStack()
    {
        this->top = NULL;
    }
    //Check two operands exist or not
    bool is_two_operands()
    {
        int counter = 0;
        Node * temp = this->top;
        while (temp != NULL && counter < 2)
        {
            counter++;
            temp = temp->next;
        }
        return counter == 2;
    }
    //Add a new element in stack
    void push(string 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";
        }
    }
    //Add a top element in stack
    string pop()
    {
        string temp = "";
        if (this->top != NULL)
        {
            temp = this->top->data;
            this->top = this->top->next;
        }
        return temp;
    }
    bool is_empty()
    {
        if (this->top != NULL)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    //Used to get top element of stack
    string peek()
    {
        if (this->top != NULL)
        {
            return this->top->data;
        }
        else
        {
            return "";
        }
    }
    int precedence(string text)
    {
        if ( text.compare("+")==0 || text.compare("-")==0 )
        {
            return 1;
        }
        else if (text.compare("*")==0 || text.compare("/")==0  )
        {
            return 2;
        }
        else if (text.compare("^")==0 )
        {
            return 3;
        }
        return -1;
    }
    bool is_operator(char text)
    {
        if (text == '+' || text == '-' || text == '*' || text == '/' || text == '^')
        {
            return true;
        }
        return false;
    }
    //Converting the given infix expression to prefix expression
    void prefix_conversion(string infix)
    {
        //Get the size
        int size = infix.size();
        //Create stack object
        MyStack collection = MyStack();
        MyStack op = MyStack();

        //Some useful variables which is using of to storing current result
        string auxiliary = "";

        string op1 = "";
        string op2 = "";
        string temp = "";
        bool is_valid = true;
        for (int i = 0; i < size && is_valid; i++)
        {
            if (infix[i] == '(')
            {
                op.push("(");
            }
            else if (this->is_operator(infix[i]))
            {
                temp = infix[i];
                //When get a operator 
                while (collection.is_two_operands() && this->precedence(temp) <= this->precedence(op.peek()))
                {
                    op1 = collection.pop();
                    op2 = collection.pop();
                    auxiliary = op.pop() + op2 + op1;
                    //Add new result into stack
                    collection.push(auxiliary);
                    
                }
                auxiliary = temp;
                op.push(auxiliary);
            }
            else if (infix[i] == ')')
            {
                if (collection.is_two_operands())
                {
                    while (collection.is_two_operands() && (op.peek()!="("))
                    {
                        op1 = collection.pop();
                        op2 = collection.pop();
                        auxiliary = op.pop() + op2 + op1;
                        //Add new result into stack
                        collection.push(auxiliary);
                        
                    }
                    op.pop();
                }
                else
                {
                    is_valid = false;
                }
            }
            else if ((infix[i] >= '0' && infix[i] <= '9') || (infix[i] >= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' && infix[i] <= 'Z'))
            {
                auxiliary = infix[i];
                collection.push(auxiliary);
            }
            else
            {

                is_valid = false;
            }
        }
        if (is_valid == false)
        {
            cout << "Invalid infix : " << infix;
        }
        else
        {
            cout << "\n Infix   : " << infix;
            cout << "\n Prefix  : " << collection.pop()<<endl;
            
        }
    }
};
int main()
{
    MyStack obj = MyStack();
    string infix = "((a*b)+(c^d))";
    obj.prefix_conversion(infix);
    infix = "((a/(b-c+d))*(e-a)*c)";
    obj.prefix_conversion(infix);

    return 0;
}

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd

 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
//Include namespace system
using System;
// C# program
// infix to prefix conversion
//Stack Node
class Node
{
	public String data;
	public Node next;
	public Node(String data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyStack
{
	public Node top;
	public MyStack()
	{
		this.top = null;
	}
	//Check two operands exist or not
	public Boolean is_two_operands()
	{
		int counter = 0;
		Node temp = this.top;
		while (temp != null && counter < 2)
		{
			counter++;
			temp = temp.next;
		}
		return counter == 2;
	}
	//Add a new element in stack
	public void push(String data)
	{
		//Make a new stack node
		Node new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = top;
			top = new_node;
		}
		else
		{
			Console.Write("Memory overflow\n");
		}
	}
	//Add a top element in stack
	public String pop()
	{
		String temp = "";
		if (top != null)
		{
			temp = top.data;
			top = top.next;
		}
		return temp;
	}
	public Boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public String peek()
	{
		if (top != null)
		{
			return top.data;
		}
		else
		{
			return "";
		}
	}
	public int precedence(String text)
	{
		if (text.Equals("+") || text.Equals("-"))
		{
			return 1;
		}
		else if (text.Equals("*") || text.Equals("/"))
		{
			return 2;
		}
		else if (text.Equals("^"))
		{
			return 3;
		}
		return -1;
	}
	public Boolean is_operator(char text)
	{
		if (text == '+' || text == '-' || text == '*' || text == '/' || text == '^')
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	public void prefix_conversion(String infix)
	{
		//Get the size
		int size = infix.Length;
		//Create stack object
		MyStack collection = new MyStack();
		MyStack op = new MyStack();
		//Some useful variables which is using of to storing current result
		String auxiliary = "";
		String op1 = "";
		String op2 = "";
		Boolean is_valid = true;
		for (int i = 0; i < size && is_valid; i++)
		{
			if (infix[i] == '(')
			{
				op.push("(");
			}
			else if (is_operator(infix[i]))
			{
				//When get a operator 
				while (collection.is_two_operands() && precedence("" + infix[i]) <= precedence(op.peek()))
				{
					op1 = collection.pop();
					op2 = collection.pop();
					auxiliary = op.pop() + op2 + op1;
					//Add new result into stack
					collection.push(auxiliary);
				}
				auxiliary = "" + infix[i];
				op.push(auxiliary);
			}
			else if (infix[i] == ')')
			{
				if (collection.is_two_operands())
				{
					while (collection.is_two_operands() && !op.peek().Equals("("))
					{
						op1 = collection.pop();
						op2 = collection.pop();
						auxiliary = op.pop() + op2 + op1;
						//Add new result into stack
						collection.push(auxiliary);
					}
					op.pop();
				}
				else
				{
					is_valid = false;
				}
			}
			else if ((infix[i] >= '0' && infix[i] <= '9') || (infix[i] >= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' && infix[i] <= 'Z'))
			{
				auxiliary = "" + infix[i];
				collection.push(auxiliary);
			}
			else
			{
				is_valid = false;
			}
		}
		if (is_valid == false)
		{
			Console.Write("Invalid infix : " + infix);
		}
		else
		{
			Console.Write("\n Infix   : " + infix);
			Console.Write("\n Prefix  : " + collection.pop());
		}
	}
	public static void Main(String[] args)
	{
		MyStack obj = new MyStack();
		String infix = "((a*b)+(c^d))";
		obj.prefix_conversion(infix);
		infix = "((a/(b-c+d))*(e-a)*c)";
		obj.prefix_conversion(infix);
	}
}

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
<?php
// Php program
// infix to prefix conversion
//Stack Node
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		$this->data = $data;
		$this->next = null;
	}
}
class MyStack
{
	public $top;

	function __construct()
	{
		$this->top = null;
	}
	//Check two operands exist or not
	public	function is_two_operands()
	{
		$counter = 0;
		$temp = $this->top;
		while ($temp != null && $counter < 2)
		{
			$counter++;
			$temp = $temp->next;
		}
		return $counter == 2;
	}
	//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";
		}
	}
	//Add a top element in stack
	public	function pop()
	{
		$temp = "";
		if ($this->top != null)
		{
			$temp = $this->top->data;
			$this->top = $this->top->next;
		}
		return $temp;
	}
	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 "";
		}
	}
	public	function precedence($text)
	{
		if ($text=="+" || $text== "-")
		{
			return 1;
		}
		else if ($text== "*" || $text=="/")
		{
			return 2;
		}
		else if ($text=="^")
		{
			return 3;
		}
		return -1;
	}
	public	function is_operator($text)
	{
		if ($text == '+' || $text == '-' || $text == '*' || $text == '/' || $text == '^')
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	public	function prefix_conversion($infix)
	{
		//Get the size
		$size = strlen($infix);
		//Create stack object
		$collection = new MyStack();
		$op = new MyStack();
		//Some useful variables which is using of to storing current result
		$auxiliary = "";
		$op1 = "";
		$op2 = "";
		$is_valid = true;
		for ($i = 0; $i < $size && $is_valid; $i++)
		{
			if ($infix[$i] == '(')
			{
				$op->push("(");
			}
			else if ($this->is_operator($infix[$i]))
			{
				//When get a operator 
				while ($collection->is_two_operands() && $this->precedence($infix[$i]) <= $this->precedence($op->peek()))
				{
					$op1 = $collection->pop();
					$op2 = $collection->pop();
					$auxiliary = $op->pop() . $op2 . $op1;
					//Add new result into stack
					$collection->push($auxiliary);
				}
				$auxiliary = "". $infix[$i];
				$op->push($auxiliary);
			}
			else if ($infix[$i] == ')')
			{
				if ($collection->is_two_operands())
				{
					while ($collection->is_two_operands() && !($op->peek()=="("))
					{
						$op1 = $collection->pop();
						$op2 = $collection->pop();
						$auxiliary = $op->pop() . $op2 . $op1;
						//Add new result into stack
						$collection->push($auxiliary);
					}
					$op->pop();
				}
				else
				{
					$is_valid = false;
				}
			}
			else if ((ord($infix[$i]) >= ord('0') 
                      && ord($infix[$i]) <= ord('9')) 
                     || (ord($infix[$i]) >= ord('a') 
                         && ord($infix[$i]) <= ord('z')) 
                     || (ord($infix[$i]) >= ord('A') 
                         && ord($infix[$i]) <= ord('Z')))
			{
				$auxiliary = $infix[$i];
				$collection->push($auxiliary);
			}
			else
			{
				$is_valid = false;
			}
		}
		if ($is_valid == false)
		{
			echo "Invalid infix : ". $infix;
		}
		else
		{
			echo "\n Infix   : ". $infix;
			echo "\n Prefix  : ". $collection->pop();
		}
	}
}

function main()
{
	$obj = new MyStack();
	$infix = "((a*b)+(c^d))";
	$obj->prefix_conversion($infix);
	$infix = "((a/(b-c+d))*(e-a)*c)";
	$obj->prefix_conversion($infix);
}
main();

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
// Node Js program
// infix to prefix conversion

//Stack Node
class Node
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyStack
{
	constructor()
	{
		this.top = null;
	}
	//Check two operands exist or not
	is_two_operands()
	{
		var counter = 0;
		var temp = this.top;
		while (temp != null && counter < 2)
		{
			counter++;
			temp = temp.next;
		}
		return counter == 2;
	}
	//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");
		}
	}
	//Add a top element in stack
	pop()
	{
		var temp = "";
		if (this.top != null)
		{
			temp = this.top.data;
			this.top = this.top.next;
		}
		return temp;
	}
	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 "";
		}
	}
	precedence(text)
	{
       
		if (text=="+" || text=="-")
		{
			return 1;
		}
		else if (text=="*" || text=="/")
		{
			return 2;
		}
		else if (text=="^")
		{
			return 3;
        }
		return -1;
	}
	is_operator(text)
	{
		if (text == '+' || text == '-' || text == '*' || text == '/' || text == '^')
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	prefix_conversion(infix)
	{
		//Get the size
		var size = infix.length;
		//Create stack object
		var collection = new MyStack();
		var op = new MyStack();
		//Some useful variables which is using of to storing current result
		var auxiliary = "";
		var op1 = "";
		var op2 = "";
		var is_valid = true;
		for (var i = 0; i < size && is_valid; i++)
		{
			if (infix[i] == '(')
			{
				op.push("(");
			}
			else if (this.is_operator(infix[i]))
			{
				//When get a operator 
				while (collection.is_two_operands() && this.precedence(infix[i]) <= this.precedence(op.peek()))
				{
					op1 = collection.pop();
					op2 = collection.pop();
					auxiliary = op.pop() + op2 + op1;
					//Add new result into stack
					collection.push(auxiliary);
				}
				auxiliary = infix[i];
				op.push(auxiliary);
			}
			else if (infix[i] == ')')
			{
				if (collection.is_two_operands())
				{
					while (collection.is_two_operands() && op.peek() != '(')
					{
						op1 = collection.pop();
						op2 = collection.pop();
						auxiliary = op.pop() + op2 + op1;
						//Add new result into stack
						collection.push(auxiliary);
					}
					op.pop();
				}
				else
				{
					is_valid = false;
				}
			}
			else if (((infix[i]).charCodeAt(0) >= ('0').charCodeAt(0) && (infix[i]).charCodeAt(0) <= ('9').charCodeAt(0)) || ((infix[i]).charCodeAt(0) >= ('a').charCodeAt(0) && (infix[i]).charCodeAt(0) <= ('z').charCodeAt(0)) || ((infix[i]).charCodeAt(0) >= ('A').charCodeAt(0) && (infix[i]).charCodeAt(0) <= ('Z').charCodeAt(0)))
			{
				auxiliary = infix[i];
				collection.push(auxiliary);
			}
			else
			{
				is_valid = false;
			}
		}
		if (is_valid == false)
		{
			process.stdout.write("Invalid infix : " + infix);
		}
		else
		{
			process.stdout.write("\n Infix   : " + infix);
			process.stdout.write("\n Prefix  : " + collection.pop());
		}
	}
}

function main()
{
	var obj = new MyStack();
	var infix = "((a*b)+(c^d))";
	obj.prefix_conversion(infix);
	infix = "((a/(b-c+d))*(e-a)*c)";
	obj.prefix_conversion(infix);
}
main();

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
#  Python 3 program
#  infix to prefix conversion

# Stack Node
class Node :
	
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class MyStack :
	
	def __init__(self) :
		self.top = None
	
	# Check two operands exist or not
	def is_two_operands(self) :
		counter = 0
		temp = self.top
		while (temp != None and counter < 2) :
			counter += 1
			temp = temp.next
		
		return counter == 2
	
	# 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 = "")
		
	
	# Add a top element in stack
	def pop(self) :
		temp = ""
		if (self.top != None) :
			temp = self.top.data
			self.top = self.top.next
		
		return temp
	
	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 ""
		
	
	def precedence(self, text) :
		if (text=="+" or text=="-") :
			return 1
		
		elif(text=="*" or text=="/") :
			return 2
		
		elif(text=="^") :
			return 3
		
		return -1
	
	def is_operator(self, text) :
		if (text == '+'
			or text == '-'
			or text == '*'
			or text == '/'
			or text == '^') :
			return True
		
		return False
	
	# Converting the given infix expression to prefix expression
	def prefix_conversion(self, infix) :
		# Get the size
		size = len(infix)
		# Create stack object
		collection = MyStack()
		op = MyStack()
		# Some useful variables which is using of to storing current result
		auxiliary = ""
		op1 = ""
		op2 = ""
		is_valid = True
		i = 0
		while (i < size and is_valid) :
			if (infix[i] == '(') :
				op.push("(")
			
			elif(self.is_operator(infix[i])) :
				# When get a operator 
				while (collection.is_two_operands() and self.precedence(infix[i]) <= self.precedence(op.peek())) :
					op1 = collection.pop()
					op2 = collection.pop()
					auxiliary = op.pop() + op2 + op1
					# Add new result into stack
					collection.push(auxiliary)
				
				auxiliary = infix[i]
				op.push(auxiliary)
			
			elif(infix[i] == ')') :
				if (collection.is_two_operands()) :
					while (collection.is_two_operands() and not op.peek()=="(") :
						op1 = collection.pop()
						op2 = collection.pop()
						auxiliary = op.pop() + op2 + op1
						# Add new result into stack
						collection.push(auxiliary)
					
					op.pop()
				else :
					is_valid = False
				
			
			elif((ord(infix[i]) >= ord('0') and ord(infix[i]) <= ord('9')) or(ord(infix[i]) >= ord('a') and ord(infix[i]) <= ord('z')) or(ord(infix[i]) >= ord('A') and ord(infix[i]) <= ord('Z'))) :
				auxiliary =  infix[i]
				collection.push(auxiliary)
			else :
				is_valid = False
			
			i += 1
		
		if (is_valid == False) :
			print("Invalid infix : ", infix, end = "")
		else :
			print("\n Infix   : ", infix, end = "")
			print("\n Prefix  : ", collection.pop(), end = "")
		
	

def main() :
	obj = MyStack()
	infix = "((a*b)+(c^d))"
	obj.prefix_conversion(infix)
	infix = "((a/(b-c+d))*(e-a)*c)"
	obj.prefix_conversion(infix)

if __name__ == "__main__": main()

Output

 Infix   :  ((a*b)+(c^d))
 Prefix  :  +*ab^cd
 Infix   :  ((a/(b-c+d))*(e-a)*c)
 Prefix  :  **/a+-bcd-eac
#  Ruby program
#  infix to prefix conversion
# Stack Node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next
    
	def initialize(data)
		self.data = data
		self.next = nil
	end
end
class MyStack 

	# Define the accessor and reader of class MyStack  
	attr_reader :top
	attr_accessor :top
	
	def initialize()
		self.top = nil
	end
	# Check two operands exist or not
	def is_two_operands()
	
		counter = 0
		temp = self.top
		while (temp != nil && counter < 2)
			counter += 1
			temp = temp.next
		end
		return counter == 2
	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 = @top
			@top = new_node
		else
		
			print("Memory overflow\n")
		end
	end
	# Add a top element in stack
	def pop()
	
		temp = ""
		if (@top != nil)
		
			temp = @top.data
			@top = @top.next
		end
		return temp
	end
	def is_empty()
	
		if (self.top != nil)
		
			return false
		else
		
			return true
		end
	end
	# Used to get top element of stack
	def peek()
	
		if (@top != nil)
		
			return @top.data
		else
		
			return ""
		end
	end
	def precedence(text)
	
		if (text=="+" || text=="-")
		
			return 1
		elsif(text=="*" || text=="/")
		
			return 2
		elsif(text=="^")
		
			return 3
		end
		return -1
	end
	def is_operator(text)
	
		if (text == '+' || text == '-' || text == '*' || text == '/' || text == '^')
		
			return true
		end
		return false
	end
	# Converting the given infix expression to prefix expression
	def prefix_conversion(infix)
	
		# Get the size
		size = infix.length()
		# Create stack object
		collection = MyStack.new()
		op = MyStack.new()
		# Some useful variables which is using of to storing current result
		auxiliary = ""
		op1 = ""
		op2 = ""
		is_valid = true
		i = 0
		while (i < size && is_valid)
		
			if (infix[i] == '(')
			
				op.push("(")
			elsif(self.is_operator(infix[i]))
			
				# When get a operator 
				while (collection.is_two_operands() && self.precedence(infix[i]) <= self.precedence(op.peek()))
				
					op1 = collection.pop()
					op2 = collection.pop()
					auxiliary = op.pop() + op2 + op1
					# Add new result into stack
					collection.push(auxiliary)
				end
				auxiliary = infix[i]
				op.push(auxiliary)
			elsif(infix[i] == ')')
			
				if (collection.is_two_operands())
				
					while (collection.is_two_operands() && op.peek()!="(")
					
						op1 = collection.pop()
						op2 = collection.pop()
						auxiliary = op.pop() + op2 + op1
						# Add new result into stack
						collection.push(auxiliary)
					end
					op.pop()
				else
				
					is_valid = false
				end
			elsif(((infix[i]).ord >= ('0').ord && (infix[i]).ord <= ('9').ord) || ((infix[i]).ord >= ('a').ord && (infix[i]).ord <= ('z').ord) || ((infix[i]).ord >= ('A').ord && (infix[i]).ord <= ('Z').ord))
			
				auxiliary = infix[i]
				collection.push(auxiliary)
			else
			
				is_valid = false
			end
			i += 1
		end
		if (is_valid == false)
		
			print("Invalid infix : ", infix)
		else
		
			print("\n Infix   : ", infix)
			print("\n Prefix  : ", collection.pop())
		end
	end
end
def main()

	obj = MyStack.new()
	infix = "((a*b)+(c^d))"
	obj.prefix_conversion(infix)
	infix = "((a/(b-c+d))*(e-a)*c)"
	obj.prefix_conversion(infix)
end
main()

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
// Scala program
// Infix to prefix conversion

//Stack Node
class Node(var data: String,
	var next: Node)
{
	def this(data: String)
	{
		this(data, null);
	}
}
class MyStack(var top: Node)
{
	def this()
	{
		this(null);
	}
	//Check two operands exist or not
	def is_two_operands(): Boolean = {
		var counter: Int = 0;
		var temp: Node = this.top;
		while (temp != null && counter < 2)
		{
			counter += 1;
			temp = temp.next;
		}
		return counter == 2;
	}
	//Add a new element in stack
	def push(data: String): Unit = {
		//Make a new stack node
		var new_node: Node = new Node(data);
		if (new_node != null)
		{
			new_node.next = top;
			top = new_node;
		}
		else
		{
			print("Memory overflow\n");
		}
	}
	//Add a top element in stack
	def pop(): String = {
		var temp: String = "";
		if (top != null)
		{
			temp = top.data;
			top = top.next;
		}
		return temp;
	}
	def is_empty(): Boolean = {
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	def peek(): String = {
		if (top != null)
		{
			return top.data;
		}
		else
		{
			return "";
		}
	}
	def precedence(text: String): Int = {
		if (text=="+" || text=="-")
		{
			return 1;
		}
		else if (text=="*" || text=="/")
		{
			return 2;
		}
		else if (text=="^")
		{
			return 3;
		}
		return -1;
	}
	def is_operator(text: Char): Boolean = {
		if (text == '+' || text == '-' || text == '*' || text == '/' || text == '^')
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	def prefix_conversion(infix: String): Unit = {
		//Get the size
		var size: Int = infix.length();
		//Create stack object
		var collection: MyStack = new MyStack();
		var op: MyStack = new MyStack();
		//Some useful variables which is using of to storing current result
		var auxiliary: String = "";
		var op1: String = "";
		var op2: String = "";
		var is_valid: Boolean = true;
		var i: Int = 0;
		while (i < size && is_valid)
		{
			if (infix(i) == '(')
			{
				op.push("(");
			}
			else if (is_operator(infix(i)))
			{
				//When get a operator 
				while (collection.is_two_operands() && precedence("" + infix(i)) <= precedence(op.peek()))
				{
					op1 = collection.pop();
					op2 = collection.pop();
					auxiliary = op.pop() + op2 + op1;
					//Add new result into stack
					collection.push(auxiliary);
				}
				auxiliary = "" + infix(i);
				op.push(auxiliary);
			}
			else if (infix(i) == ')')
			{
				if (collection.is_two_operands())
				{
					while (collection.is_two_operands() && !op.peek().equals("("))
					{
						op1 = collection.pop();
						op2 = collection.pop();
						auxiliary = op.pop() + op2 + op1;
						//Add new result into stack
						collection.push(auxiliary);
					}
					op.pop();
				}
				else
				{
					is_valid = false;
				}
			}
			else if ((infix(i) >= '0' && infix(i) <= '9') || (infix(i) >= 'a' && infix(i) <= 'z') || (infix(i) >= 'A' && infix(i) <= 'Z'))
			{
				auxiliary = "" + infix(i);
				collection.push(auxiliary);
			}
			else
			{
				is_valid = false;
			}
			i += 1;
		}
		if (is_valid == false)
		{
			print("Invalid infix : " + infix);
		}
		else
		{
			print("\n Infix   : " + infix);
			print("\n Prefix  : " + collection.pop());
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyStack = new MyStack();
		var infix: String = "((a*b)+(c^d))";
		obj.prefix_conversion(infix);
		infix = "((a/(b-c+d))*(e-a)*c)";
		obj.prefix_conversion(infix);
	}
}

Output

 Infix   : ((a*b)+(c^d))
 Prefix  : +*ab^cd
 Infix   : ((a/(b-c+d))*(e-a)*c)
 Prefix  : **/a+-bcd-eac
// Swift program
// infix to prefix conversion
//Stack Node
class Node
{
	var data: String;
	var next: Node? ;
	init(_ data: String)
	{
		self.data = data;
		self.next = nil;
	}
}
class MyStack
{
	var top: Node? ;
	init()
	{
		self.top = nil;
	}
	//Check two operands exist or not
	func is_two_operands() -> Bool
	{
		var counter: Int = 0;
		var temp: Node? = self.top;
		while (temp != nil && counter < 2)
		{
			counter += 1;
			temp = temp!.next;
		}
		return counter == 2;
	}
	//Add a new element in stack
	func push(_ data: String)
	{
		//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: "");
		}
	}
	//Add a top element in stack
	func pop() -> String
	{
		var temp: String = "";
		if (self.top != nil)
		{
			temp = self.top!.data;
			self.top = self.top!.next;
		}
		return temp;
	}
	func is_empty() -> Bool
	{
		if (self.top != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	func peek() -> String
	{
		if (self.top != nil)
		{
			return self.top!.data;
		}
		else
		{
			return "";
		}
	}
	func precedence(_ text: String) -> Int
	{
		if (text=="+" || text=="-")
		{
			return 1;
		}
		else if (text=="*" || text=="/")
		{
			return 2;
		}
		else if (text=="^")
		{
			return 3;
		}
		return -1;
	}
	func is_operator(_ text: Character) -> Bool
	{
		if (text == "+" || text == "-" || text == "*" || text == "/" || text == "^")
		{
			return true;
		}
		return false;
	}
	//Converting the given infix expression to prefix expression
	func prefix_conversion(_ exp: String)
	{
        let infix = Array(exp);
		//Get the size
		let size: Int = infix.count;
		//Create stack object
		let collection: MyStack = MyStack();
		let op: MyStack = MyStack();
		//Some useful variables which is using of to storing current result
		var auxiliary: String = "";
		var op1: String = "";
		var op2: String = "";
		var is_valid: Bool = true;
		var i: Int = 0;
		while (i < size && is_valid)
		{
			if (infix[i] == "(")
			{
				op.push("(");
			}
			else if (self.is_operator(infix[i]))
			{
				//When get a operator 
				while (collection.is_two_operands() && self.precedence(String(infix[i])) <= self.precedence(op.peek()))
				{
					op1 = collection.pop();
					op2 = collection.pop();
					auxiliary = op.pop() + op2 + op1;
					//Add new result into stack
					collection.push(auxiliary);
				}
				auxiliary = String(infix[i]);
				op.push(auxiliary);
			}
			else if (infix[i] == ")")
			{
				if (collection.is_two_operands())
				{
					while (collection.is_two_operands() && op.peek() != "(")
					{
						op1 = collection.pop();
						op2 = collection.pop();
						auxiliary = op.pop() + op2 + op1;
						//Add new result into stack
						collection.push(auxiliary);
					}
					let _ = op.pop();
				}
				else
				{
					is_valid = false;
				}
			}
			else if ((infix[i] >= "0" && infix[i] <= "9") || (infix[i] >= "a" && infix[i] <= "z") || (infix[i] >= "A" && infix[i] <= "Z"))
			{
				auxiliary = String(infix[i]);
				collection.push(auxiliary);
			}
			else
			{
				is_valid = false;
			}
			i += 1;
		}
		if (is_valid == false)
		{
			print("Invalid infix : ", infix, terminator: "");
		}
		else
		{
			print("\n Infix   : ", exp, terminator: "");
			print("\n Prefix  : ", collection.pop(), terminator: "");
		}
	}
}
func main()
{
	let obj: MyStack = MyStack();
	var infix: String = "((a*b)+(c^d))";
	obj.prefix_conversion(infix);
	infix = "((a/(b-c+d))*(e-a)*c)";
	obj.prefix_conversion(infix);
}
main();

Output

 Infix   :  ((a*b)+(c^d))
 Prefix  :  +*ab^cd
 Infix   :  ((a/(b-c+d))*(e-a)*c)
 Prefix  :  **/a+-bcd-eac

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.

New Comment







© 2021, kalkicode.com, All rights reserved