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-
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