Skip to main content

Infix to postfix conversion using stack in typescript

Ts program for Infix to postfix conversion using stack. Here problem description and explanation.

// TypeScript program for
// Infix to postfix conversion
// Using custom stack

// 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 pop()
	{
		if (this.size > 0 && this.top != null)
		{
			var temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			this.size--;
		}
	}
	// 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 is_operator(text: string)
	{
		if (text == '+' || text == '-' || text == '*' || 
            text == '/' || text == '^')
		{
			return true;
		}
		return false;
	}
	// Converting the given infix expression to postfix expression
	public infixToPostfix(infix: string)
	{
		var result = "";
		// Get the size
		var size = infix.length;
		// Create empty stack 
		var s = new MyStack();
		for (var i = 0; i < size; ++i)
		{
			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'))
			{
				// When getting a operands
				result = result + infix.charAt(i);
			}
			else
			{
				if (s.isEmpty() || infix.charAt(i) == '(')
				{
					// Base case
					// When getting a open parenthesis
					// Or stack is empty
					s.push(infix.charAt(i));
				}
				else if (infix.charAt(i) == ')')
				{
					// Need to remove stack element until the close bracket
					while (s.isEmpty() == false && 
                           s.peek() != '(')
					{
						// Get top element
						result += s.peek();
						// Remove stack element
						s.pop();
					}
					if (s.peek() == '(')
					{
						// Remove stack element
						s.pop();
					}
				}
				else
				{
					// Remove stack element until precedence of 
					// top is greater than current infix operator
					while (s.isEmpty() == false && 
                           this.precedence(infix.charAt(i)) <= 
                           this.precedence(s.peek()))
					{
						// Get top element
						result += s.peek();
						// Remove stack element
						s.pop();
					}
					// Add new operator
					s.push(infix.charAt(i));
				}
			}
		}
		// Add remaining elements
		while (s.isEmpty() == false)
		{
			result += s.peek();
			s.pop();
		}
		// Display result
		console.log(" Infix    : " + infix);
		console.log(" Postfix  : " + result);
	}
	public static main(args: string[])
	{
		var task = new Conversion();
		var infix = "((a/b+c))/(e*f)+(g^h-i)+k";
		task.infixToPostfix(infix);
		infix = "((a*b)^(c+d)/e)-f";
		task.infixToPostfix(infix);
	}
}
Conversion.main([]);
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

Output

 Infix    : ((a/b+c))/(e*f)+(g^h-i)+k
 Postfix  : ab/c+ef*/gh^i-+k+
 Infix    : ((a*b)^(c+d)/e)-f
 Postfix  : ab*cd+^e/f-




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