Posted on by Kalkicode
Code Stack

Infix to prefix conversion using stack in typescript

Ts program for Infix to prefix conversion using stack. Here problem description and other solutions.

// TypeScript program for
// Infix to prefix conversion

// Stack node
class StackNode
{
	// Stack data
	public element: string;
	public next: StackNode;
	constructor(element: string, next: StackNode)
	{
		this.element = element;
		this.next = next;
	}
}
// Define a custom stack
class MyStack
{
	public top: StackNode;
	public size: number;
	constructor()
	{
		// Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	public push(element: string)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	public boolean isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public string pop()
	{
		var c = "";
		if (this.size > 0 && this.top != null)
		{
			var temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			this.size--;
			c = temp.element;
		}
		return c;
	}
	// Return top element of stack
	public string peek()
	{
		if (this.top == null)
		{
			return "";
		}
		return this.top.element;
	}
}
class Conversion
{
	public number precedence(text: string)
	{
		if (text=="+" || text=="-")
		{
			return 1;
		}
		else if (text=="*" || text=="/")
		{
			return 2;
		}
		else if (text=="^")
		{
			return 3;
		}
		return -1;
	}
	public boolean isOperator(text: string)
	{
		if (this.precedence(text) != -1)
		{
			return true;
		}
		return false;
	}
	// Converting the given infix 
	// expression to prefix expression
	public infixToPrefix(infix: string)
	{
		// Get the size
		var size = infix.length;
		// Create stack object
		var s = new MyStack();
		var op = new MyStack();
		// Some useful variables which is using of to 
		// storing current result
		var auxiliary = "";
		var op1 = "";
		var op2 = "";
		var isValid = true;
		for (var i = 0; i < size && isValid; i++)
		{
			if (infix.charAt(i) == '(')
			{
				op.push("(");
			}
			else if (this.isOperator(infix.charAt(i)) == true)
			{
				// When get a operator 
				while (s.size > 1 && this.precedence(
                  infix.charAt(i)) <= this.precedence(op.peek()))
				{
					op1 = s.pop();
					op2 = s.pop();
					auxiliary = op.pop() + op2 + op1;
					// Add new result into stack
					s.push(auxiliary);
				}
				auxiliary = infix.charAt(i);
				op.push(auxiliary);
			}
			else if (infix.charAt(i) == ')')
			{
				if (s.size > 1)
				{
					while (s.size > 1 && op.peek()!=("("))
					{
						op1 = s.pop();
						op2 = s.pop();
						auxiliary = op.pop() + op2 + op1;
						// Add new result into stack
						s.push(auxiliary);
					}
					op.pop();
				}
				else
				{
					isValid = 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);
				s.push(auxiliary);
			}
			else
			{
				isValid = false;
			}
		}
		if (isValid == false)
		{
			console.log("Invalid infix : " + infix);
		}
		else
		{
			// Display result
			console.log(" Infix   : " + infix);
			console.log(" Prefix  : " + s.pop());
		}
	}
	public static main(args: string[])
	{
		var task = new Conversion();
		// Test
		var infix = "((a*b)+(c^d))";
		task.infixToPrefix(infix);
		infix = "((a/(b-c+d))*(e-a)*c)";
		task.infixToPrefix(infix);
	}
}
Conversion.main([]);
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

Output

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

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.

New Comment