You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
/* A stack is a data structure that holds a list of elements. A stack works based on the LIFO principle meaning that the most recently added element is the first one to remove.
2
+
3
+
It has two main operations that occur only at the top of the stack: push and pop. The push operation places an element at the top of stack whereas the pop operation removes an element from the top of the stack. */
4
+
5
+
functionStack(){
6
+
7
+
this.count=0;
8
+
this.obj={};
9
+
}
10
+
11
+
// Adding a value at the top of the stack. And the key of the object will be the current value of count. And the new value that I am pushing will be the value of that key-value pair.
12
+
13
+
Stack.prototype.push=function(value){
14
+
this.obj[this.count]=value;
15
+
this.count++;
16
+
}
17
+
18
+
// remove, or pop out the top-most value from the stack
19
+
Stack.prototype.pop=function(){
20
+
if(this.count===0){
21
+
returnundefined;
22
+
}
23
+
this.count--;
24
+
letresult=this.obj[this.count];// Hook-up to the key of the object that I will remove
25
+
deletethis.obj[this.count];
26
+
returnresult;
27
+
}
28
+
29
+
// return the length of the stack, which is the size or how many items were inserted
// Arrow functions cannot be used as methods or constructors - so, I changed my earlier constructor with arrows to regular function in this class
2
+
3
+
classStack{
4
+
constructor(){
5
+
this.data=[];
6
+
}
7
+
8
+
pop()
9
+
{
10
+
// return top most element in the stack
11
+
// and removes it from the stack
12
+
// Underflow if stack is empty
13
+
if(this.data.length==0){
14
+
return"Underflow";
15
+
}else{
16
+
returnthis.data.pop();
17
+
}
18
+
}
19
+
20
+
top(){
21
+
returnthis.data.length;
22
+
}
23
+
24
+
push(...element){
25
+
for(variofelement){
26
+
returnthis.data.push(i)
27
+
}
28
+
}
29
+
30
+
// peek() method looks at the object at the top of this stack without removing it from the stack. The stack is not modified (it does not remove the element; it only returns the element for information purposes).
31
+
32
+
peek(){
33
+
returnthis.data[this.data.length-1];
34
+
}
35
+
36
+
clear(){
37
+
returnthis.data=[];
38
+
}
39
+
40
+
length(){
41
+
returnthis.data.length;
42
+
}
43
+
44
+
search(value){
45
+
for(leti=0;i<this.data.length;i++){
46
+
if(this.data[i]===value){
47
+
returnvalue;
48
+
}else{
49
+
returnfalse;
50
+
}
51
+
}
52
+
}
53
+
}
54
+
55
+
// Parenthesis matching function to return true or false
56
+
57
+
functionisParenthesisMatched(str){
58
+
59
+
letstack=newStack();
60
+
61
+
letopeningParenthesis=["[","(","{"];
62
+
letclosingParenthesis=["]",")","}"];
63
+
64
+
/* For each element of the string argument, iterate through each element > check if the current element is any of the opening parenthesis array > If true, push it to stack > IF NOT > there could be 3 cases i.e. ], ), }
65
+
> check all the 3 cases switching through them > and comparing this current closing parenthesis with the top element from the stack. Note, that I have only pushed elements from the opening parenthesis to the stack.
66
+
> If any match is found from in the closingParenthesis array and the top-most element from stack, then just pop that element from stack. And apply break for this iteration.
67
+
> So, for each of the
68
+
69
+
Explanation that checking only the top-most element of the stack with the closing parenthesis is enough
70
+
71
+
By the design of this code, I am only making sure that to return true from this function, either (A) all the opening parenthesis will come first ( like in this case - "{[( )]}" ) - or (B) corresponding matching parenthesis will come one after another (side by side) ( like in case "{()}[]" )
72
+
73
+
In the first case A - The first time I hit a closing parenthesis, the switch function will switch cases, through the 3 of them, and first will pop-out the "(" parenthesis - as the closing ")" will be matched.
74
+
Then the next iteration will pop-out the straight bracket "[" - as that will be matched. And lastly the left over curly brace "{"
75
+
76
+
B> And in the case "{()}[]" - Its eazy to see that the part "{()}" is same as the case-A above, and the part "[ ]" is obvious that the peek element will be the only possible matching element to pop out from the stack.
77
+
78
+
And with the above code, third case, that this code will return false, is when although there are matched parenthesis
A postfix expression evaluator works on arithmetic expressions taking the following form:
3
+
op1 op2 operator
4
+
Using two stacks — one for the operands and one for the operators — design and implement a JavaScript function that converts infix expressions to postfix expressions, and then use the stacks to evaluate the expression.
5
+
6
+
Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
7
+
Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
8
+
9
+
======================
10
+
11
+
Problem - Statement -
12
+
13
+
Construct a function named toPostfix that, when given a string containing an expression in infix notation, will return an identical expression in postfix notation.
14
+
15
+
The operators used will be '+', '-', '*', '/', and '^' with standard precedence rules and left-associativity (meaning the operations are grouped from the left) of all operators but "^".
16
+
17
+
toPostfix("2+7*5"); // Should return "275*+"
18
+
toPostfix("3*3/(7+1)"); // Should return "33*71+/"
19
+
toPostfix("5+(6-2)*9+3^(7-1)"); // Should return "562-9*+371-^+"
20
+
21
+
======================
22
+
23
+
THe Algo https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
24
+
25
+
1. Scan the infix expression from left to right.
26
+
27
+
2. If the scanned character is an operand, push it to the result array.
28
+
29
+
3. Else if the scanned character is a operator
30
+
31
+
3.1 If the precedence of the scanned operator is greater than the precedence of the top-most operator in the stack(or the stack is empty), push it. NOTE - A OPERATOR WITH HIGHER ORDER IS EXECUTED FIRST PER PEMDAS / BODMAS RULE
32
+
33
+
3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
34
+
35
+
4. If the scanned character is an ‘(‘, push it to the stack.
36
+
37
+
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
38
+
39
+
6. Repeat steps 2-6 until infix expression is scanned.
40
+
41
+
7. Pop and output from the stack until it is not empty.
42
+
*/
43
+
44
+
functiontoPostfix(infix){
45
+
46
+
letoperatorsObj={
47
+
'^':{
48
+
precedence:4,
49
+
left:false
50
+
},
51
+
'*':{
52
+
precedence:3,
53
+
left:true
54
+
},
55
+
'/':{
56
+
precedence:3,
57
+
left:true
58
+
},
59
+
'+':{
60
+
precedence:2,
61
+
left:true
62
+
},
63
+
'-':{
64
+
precedence:2,
65
+
left:true
66
+
},
67
+
};
68
+
69
+
letpostfix="";// This is the final string after denoting the expression in postfix format
70
+
letoperations=[]// This array containing all the 5 individual operations
71
+
72
+
// start scanning through each of the element of the given expression i.e. the argument 'infix' which in the callback funciton to forEach will be represented by the variable element.
73
+
74
+
infix.split("").forEach(function(element){
75
+
76
+
// first if the current element is a number and not a operator or not a "(" or ")"
77
+
if(!isNaN(parseInt(element))){
78
+
postfix+=element;
79
+
}
80
+
// Now if current element is an operator, i.e. one of the 5 properties of operatorsObj is 'true'