Stack

Question 1

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Answer 1

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const START_PARENT = ['(', '[', '{'];
    const stack = [];

if (s.length % 2 !== 0) {
    return false;
}

    for (let i = 0; i < s.length; i++) {
        const value = s[i];
        if (START_PARENT.includes(value)) {
            stack.push(value);
        } else {
            const lastOpenedParent = stack.pop();
            if ((value === ')' &amp;&amp; lastOpenedParent !== '(')
                || (value === '}' &amp;&amp; lastOpenedParent !== '{')
                || (value === ']' &amp;&amp; lastOpenedParent !== '[')
               ) {
                return false;
            }
        }
    }
    return stack.length === 0;    
};

Question 2

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: S = “ab#c”, T = “ad#c”
Output: true
Explanation: Both S and T become “ac”.
Example 2:

Input: S = “ab##”, T = “c#d#”
Output: true
Explanation: Both S and T become “”.

Answer 2

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
const getStringWithoutBackspace = function(s) {
    let res = '';
    const BACKSPACE = '#';

    for (let i = 0; i < s.length; i++) {
        if (s[i] !== BACKSPACE) {
            res += s[i];
        } else {
            res = res.substr(0, res.length - 1);
        }
    }

    return res;
}
var backspaceCompare = function(S, T) {
    return getStringWithoutBackspace(S) === getStringWithoutBackspace(T);
};

Question 3

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:

Input: [“2”, “1”, “+”, “3”, “*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Answer 3

/**
* @param {string[]} tokens
* @return {number}
/
var evalRPN = function(tokens) {
const stack = [];
let op1;
let op2;
for (let i = 0; i < tokens.length; i++) {
if (!isNaN(Number(tokens[i]))) {
stack.push(Number(tokens[i]));
} else {
op1 = stack.pop();
op2 = stack.pop();
console.log(tokens[i], op1, op2);
if (tokens[i] === ‘+’) {
stack.push(op1 + op2);
} else if(tokens[i] === ‘-‘) {
stack.push(op2 - op1);
} else if (tokens[i] === ‘’) {
stack.push(op1 * op2);
} else if (tokens[i] == ‘/’) {
if (Math.abs(op2) > Math.abs(op1)) {
stack.push(Math.floor(op2 / op1));
} else {
stack.push(Math.round(op2 / op1));
}
}
}
}
return stack.pop();
};