Arithmetic Expression Evaluation

Types of Arithmetic expression

Infix expression

We, humans, understand operators + , - , * , / , ^ precedence and based on that we evaluate 100 * 2 + 12 as 212 .

1. Highest: Exponentiation (^)
2. Next highest: Multiplication (*) and division (/)
3. Lowest: Addition (+) and Subtraction (-)

But what if we can evaluate expression without knowing the operator's precedence?

In that case, humans need to use parenthesis to avoid confusion. It means 100 * 2 + 12 should be either represented as 100 * (2 + 12) evaluated as 1400or (100 * 2) + 12 evaluated as 212 . This presentation of an arithmetic expression is known as infix .

Infix is good for humans but expensive for computers. Therefore we will learn about other computer-friendly expressions as well.

Prefix notation

The operator is placed before operands i.e. 100*2 is written as * 100 2 .

Postfix notation

The operator is placed after the operands i.e. 100*2 is written as 100 2 *

Algorithm to evaluate infix expression

https://leetcode.com/problems/basic-calculator-ii/description/

The intuition behind evaluating the infix expression 100*2+12+20 vs 100 + 2 * 12+20

1. We delay the evaluation until we find the operator with lower precedence.
2. I.e if we first see + then we don’t want to calculate for now.
3. If the next is with a higher precedence * then again we don’t want to evaluate.
4. If the next is a lower precedence then evaluate all the operators with higher precedence.

How can we implement it?

1. Delaying operator evaluation means we need to keep it somewhere.
2. Wait for a lower presence operator means we need to maintain the monotonic increasing stack in terms of operator precedence.
3. We need to maintain another stack for operands to choose when the operator is ready to evaluate.

Based on this, we can define the algorithm as below.

1. Define operator stack and operand stack.
2. Scan expression from left to right.
3. If a character is operand then add to the operand stack.
4. If a character is an operator and the operator stack is empty then add it.
5. Otherwise, if the new operator precedence is higher than the top of the operator stack then add it.
6. Otherwise if lower then keep processing it until the top of an operator is a higher precedence.

Following is the code to implement this.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])
const doProcessing = (valueStack, opStack) => {
    const op = opStack.pop();
    const b = valueStack.pop();
    const a = valueStack.pop();
    switch(op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return Math.trunc(a/b);
    }
}
const calculateUsingTwoStack = s => {
    const n = s.length;
    if(n === 0) {
        return 0;
    }
    const valueStack = [];
    const opStack = [];
    const operator = new Map([['(',0],['-',1],['+',1],['*',2],['/',2]]);
    for (let i =0; i < n; i++) {
        const chr  = s[i];
        // skip empty space
        if(chr === ' ') {
            continue;
        }
        // if number, add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i+1]) ) {
                i++;
                temp.push(s[i]);
            }
            const num = temp.join('');
            
            // scan rest of digit
            valueStack.push(parseInt(num, 10));
            continue;
        }
        // if opening paranthesis then add into operator stack
        if(chr === '(') {
            opStack.push(chr);
            continue;
        }
        // if closing paranthesis 
        if (chr === ')') {
            // keep processing until find opening paran
            while(opStack[opStack.length-1] !=='(') {
                valueStack.push(doProcessing(valueStack, opStack));
            }
            // pop one more time to remove opening paran
            opStack.pop();
            continue;
        } 
        // if operator
        if(operator.has(chr)) {
            
            // if operator then before add into opstack, eval higher/eq precence first
            while(operator.get(opStack[opStack.length-1]) >= operator.get(chr)) {
                valueStack.push(doProcessing(valueStack, opStack));
            }
            // Add operator into stack
            opStack.push(chr);            
        }

    }

    // eval rest
    while(opStack.length > 0) {
       valueStack.push(doProcessing(valueStack, opStack)); 
    }
    return valueStack.pop();    
}
/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
    return calculateUsingTwoStack(s);
};

Algorithm to evaluate prefix/postfix expression

1. Prefix and Postfix expressions can be evaluated faster than an infix expression.
2. This is because we don’t need to process any brackets or follow the operator precedence rule.
3. In postfix and prefix expressions whichever operator comes before will be evaluated first, irrespective of its priority.
4. Also, there are no brackets in these expressions.
5. As long as we can guarantee that a valid prefix or postfix expression is used, it can be evaluated with correctness.

Note1: To process multi digits, we need a separator for example space.

Note 2: Prefix scan input from right to left and postfix scan input from left to right, the rest of the steps are the same for both.

Following is the code for prefix expression evaluation which scans expression from right to left.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])
const doProcessing = (valueStack, op) => {
    // order of operand matter for division operator
    const b = valueStack.pop(); // b will be on top
    const a = valueStack.pop(); // a will be next
    switch(op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return Math.trunc(a/b);
    }
}
/**
 * @param {string} s
 * @return {number}
 */
const prefixExpression = s => {
    const n = s.length;
    if(n === 0) {
        return 0;
    }
    const valueStack = [];
    for (let i =n-1; i >=0; i--) {
        const chr  = s[i];
        // if space as separator then skip it as digits must have scanned earlier
        if(chr === ' ') {
          continue;
        }
        // if number, keep scanning until find separator and then add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i-1]) ) {
                i--; // move left
                temp.push(s[i]);
            }
            // reverse as we scanned from right to left
            const num = temp.join('');
            
            // push to stack
            valueStack.push(parseInt(num, 10));
            continue;
        }

        // if operator
        if(!digits.has(chr)) {
            // If operator then process it
            valueStack.push(doProcessing(valueStack, chr))         
        }
    }
    return valueStack.pop();    
}

Following is the code for postfix expression evaluation which scans the expression from left to right.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])
const doProcessing = (valueStack, op) => {
    // order of operand matter for division operator
    const b = valueStack.pop(); // b will be on top
    const a = valueStack.pop(); // a will be next
    switch(op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return Math.trunc(a/b);
    }
}
/**
 * @param {string} s
 * @return {number}
 */
const postfixExpression = s => {
    const n = s.length;
    if(n === 0) {
        return 0;
    }
    const valueStack = [];
    for (let i =0; i < n; i++) {
        const chr  = s[i];
        // if space as separator then skip it as digits must have scanned earlier
        if(chr === ' ') {
          continue;
        }
        // if number, keep scanning until find separator and then add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i-1]) ) {
                i++; // move right
                temp.push(s[i]);
            }
            const num = temp.join('');
            
            // push to stack
            valueStack.push(parseInt(num, 10));
            continue;
        }

        // if operator
        if(!digits.has(chr)) {
            // If operator then process it
            valueStack.push(doProcessing(valueStack, chr))         
        }
    }
    return valueStack.pop();    
}

Convert infix expression into postfix expression

1. Similar to infix expression evaluation, we will use a monotonic increasing operator stack to keep the operator in precedence and only process if the lower operator has arrived.
2. Since the goal here is not to evaluate infix expression therefore operand stack is not required.
3. Instead, we will need ans=[] to keep adding operands. Also, processing of the operator is nothing but adding it into an array.
4. Since infix expression might have parenthesis therefore we need to handle it as well.
5. Space will be used as a separator to support multiple digits.

Following is the code to implement it.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])
/**
 * @param {string} s
 * @return {string}
 */
const infixToPostfixExpression = s => {
    const n = s.length;
    if(n === 0) {
        return '';
    }
    const ans = [];
    const opStack = [];
    const operator = new Map([['(',0],['-',1],['+',1],['*',2],['/',2]]);
    for (let i =0; i < n; i++) {
        const chr  = s[i];
        // skip empty space
        if(chr === ' ') {
            continue;
        }
        // if number, add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i+1]) ) {
                i++;
                temp.push(s[i]);
            }
            const num = temp.join('');
            
            // Add operator into ans
            ans.push(parseInt(num, 10));
            continue;
        }
        // if opening paranthesis then add into operator stack
        if(chr === '(') {
            opStack.push(chr);
            continue;
        }
        // if closing paranthesis 
        if (chr === ')') {
            // keep processing until find opening paran
            while(opStack[opStack.length-1] !=='(') {
                ans.push(opStack.pop());
            }
            // pop one more time to remove opening paran
            opStack.pop();
            continue;
        } 
        // if operator
        if(operator.has(chr)) {
            
            // if operator then before add into opstack, eval higher/eq precence first
            while(operator.get(opStack[opStack.length-1]) >= operator.get(chr)) {
                ans.push(opStack.pop());
            }
            // Add operator into stack
            opStack.push(chr);            
        }
    }

    // eval rest
    while(opStack.length > 0) {
       ans.push(opStack.pop());
    }
    return ans.join(''); 
}

Convert infix to prefix expression

Special care in postfix conversion steps

1. Since we have reversed the order therefore ( must be handled as ) & ) as ( .
2. Due to the reversal of the infix string, the left-to-right associativity gets disturbed. To handle it, instead of using the pop operation to pop operators with greater than or equal precedence, here we will only pop the operators from the stack that have greater precedence.
3. Due to reversal, multi digits will be reversed as well, reversed again to parse the number.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])
/**
 * Modified infix to postfix to handle the reversed string
 * @param {string} s - reversed input
 * @return {string[]}
 */
const infixToPostfixExpression = s => {
    const n = s.length;
    if(n === 0) {
        return '';
    }
    const ans = [];
    const opStack = [];
    const operator = new Map([['(',0],['-',1],['+',1],['*',2],['/',2]]);
    for (let i =0; i < n; i++) {
        const chr  = s[i];
        // skip empty space
        if(chr === ' ') {
            continue;
        }
        // if number, add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i+1]) ) {
                i++;
                temp.push(s[i]);
            }
            const num = temp.reverse().join(''); // Handle reverse string
            
            // Add operator into ans
            ans.push(parseInt(num, 10));
            continue;
        }
        // if closing (to handle reverse input) paranthesis then add into operator stack
        if(chr === ')') {
            opStack.push(chr);
            continue;
        }
        // if opening (to handle reverse input) paranthesis 
        if (chr === '(') {
            // keep processing until find opening paran
            while(opStack[opStack.length-1] !==')') {
                ans.push(opStack.pop());
            }
            // pop one more time to remove opening paran
            opStack.pop();
            continue;
        } 
        // if operator
        if(operator.has(chr)) {
            
            // if operator then before add into opstack, eval higher/eq precence first
            // Do not apply = to handle reverse input
            while(operator.get(opStack[opStack.length-1]) > operator.get(chr)) {
                ans.push(opStack.pop());
            }
            // Add operator into stack
            opStack.push(chr);            
        }
    }

    // eval rest
    while(opStack.length > 0) {
       ans.push(opStack.pop());
    }
    return ans; 
}
/**
 * @param {string} s
 * @return {string}
 */
const infixToPrefixExpression = s => {
    // reverse input and call modified infixToPostfixExpression
    const postfix= infixToPostfixExpression(s.split('').reverse().join(''));
    return postfix.reverse().join('');
}

Expression Tree

1. The expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand.
2. In order traversal of expression tree produces infix version of given postfix expression.
3. Postorder traversal gives postfix expression.

Evaluate Expression Tree

1. Postfix expression is easy to evaluate using stack.
2. Postorder traversal of expression tree gives postfix expression.
3. Postorder traversal (dfs) uses recursion which is an internally use stack therefore we can simulate the postfix expression evaluation.
4. Therefore we can simply use postorder traversal to evaluate the expression tree.

const doProcessing = (a, b, op) => {
    switch(op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return Math.trunc(a/b);
    }
}
const dfs = node => {
  const value = node.value;
  // leaf node means operand so simply return the parsed value.
  if(!node.left && !node.right) {
    return parseInt(value, 10);   
  }
  // operand will always have left and right child
  const a = dfs(node.left);
  const b = dfs(node.right);
  // post order processing here as node is operator
  return doProcessing(a, b, value);
}
const solve = root => {
 if(!root) {
    return 0;
  }
  return dfs(root);
}

Construction of expression tree from postfix expression

Postfix expression is easy to convert into an expression tree. Following is the algorithm.

1. If a character is an operand push that into the stack as a node.
2. If a character is an operator pop two values from the stack make them its child and push the current node into the stack.
3. In the end, the only element of the stack will be the root of an expression tree.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])

/**
 * @param {string} s
 * @return {Node}
 */
const postfixToExpressionTree = s => {
    const n = s.length;
    if(n === 0) {
        return null;
    }
    const nodeStack = [];
    for (let i =0; i < n; i++) {
        const chr  = s[i];
        // if space as separator then skip it as digits must have scanned earlier
        if(chr === ' ') {
          continue;
        }
        // if number, keep scanning until find separator and then add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i-1]) ) {
                i++; // move right
                temp.push(s[i]);
            }
            const num = temp.join('');
            
            // Build node and push to stack
            const node = new Node(parseInt(num, 10)) 
            nodeStack.push(node);
            continue;
        }

        // if operator
        if(!digits.has(chr)) {
            // If operator then pop last two operand node to build this node
            const node = new Node(chr);
            node.right = nodeStack.pop(); // right will be on top
            node.left = nodeStack.pop(); // left will be next 
            nodeStack.push(node);
        }
    }
    // Last value in the stack will be the root
    return nodeStack.pop();    
}

Construction of expression tree from prefix expression

As we know, the difference between postfix and prefix expression evaluation is only the order we scan. I.e. in postfix we scan input from left to right and in prefix we scan from right to left.

Here as well we can simply scan input form right to left and apply the same algorithm.

const digits = new Set(['0','1','2','3','4','5','6','7','8','9'])

/**
 * @param {string} s
 * @return {Node}
 */
const infixToExpressionTree = s => {
    const n = s.length;
    if(n === 0) {
        return null;
    }
    const nodeStack = [];
    for (let i =n-1; i >= 0; i--) {
        const chr  = s[i];
        // if space as separator then skip it as digits must have scanned earlier
        if(chr === ' ') {
          continue;
        }
        // if number, keep scanning until find separator and then add into value stack
        if(digits.has(chr)) {
            const temp = [chr];
            while( digits.has(s[i-1]) ) {
                i++; // move right
                temp.push(s[i]);
            }
            // Reverse as we scan from right to left
            const num = temp.reverse().join('');
            
            // Build ndoe and push to stack
            const node = new Node(parseInt(num, 10)) 
            nodeStack.push(node);
            continue;
        }

        // if operator
        if(!digits.has(chr)) {
            // If operator then pop last two operand node to build this node
            // Since we scanned from right to left therefore stack order is also changed
            const left = nodeStack.pop();  
            const right = nodeStack.pop();   
            const node = new Node(chr);
            node.left = left;
            node.right = right;
            nodeStack.push(node);
        }
    }
    // Last value in the stack will be the root
    return nodeStack.pop();    
}

Expression tree to postfix expression

We can simply run postorder dfs traversal.

const solve = root=> {
  if(!root) {
    return '';
  }
  const ans = [];
  const dfs = node => {
   if(node.left){
      dfs(node.left);
    }
    if(node.right) {
      dfs(node.right);
    }
    // post order traversal
    ans.push(node.value); 
  }
  dfs(root);
  return ans.join(' ');
}

Expression tree to infix expression

We can simply run in order dfs traversal.

const solve = root=> {
  if(!root) {
    return '';
  }
  const ans = [];
  const dfs = node => {
   if(node.left){
      dfs(node.left);
    }
    // inorder traversal
    ans.push(node.value);
    if(node.right) {
      dfs(node.right);
    }
  }
  dfs(root);
  return ans.join(' ');
}

Expression tree to prefix expression

We can simply run pre order dfs traversal.

const solve = root=> {
  if(!root) {
    return '';
  }
  const ans = [];
  const dfs = node => {
    // preorder traversal
    ans.push(node.value);

   if(node.left){
      dfs(node.left);
    }

    if(node.right) {
      dfs(node.right);
    }
  }
  dfs(root);
  return ans.join(' ');
}

Build expression to evaluate the given target

https://leetcode.com/problems/expression-add-operators/description/

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Approach

Generate all expressions

To generate all possible expressions, we can write following recursion function.

f(i,slate) = Generate expressions for num in range of (i,....n-1)
           = Here slate as string has solution so far from (0,....i-1)
f(i,slate) = Try all substring starting from j=i....to j=n-1
f(i, slate) {
  if i===n // This is ans zone
  for j=i....n-1
    f(j+1, slate+ num.substring(i,j+1) + op);
}

Why not to use slate as array?

Currently slate used as string. It means every string operation is creating a new copy that leads to high memory usage.

Ideally we can covert it into array, but that would lead to extra code to take care of backtracking cleanup.

Order to update slate

In the recursion function, we can update slate as either #1:slate+ op + val or #2: slate+ val + op .

If we go with #1 then at i=0 it is not a valid position to apply operator.

If we go with #2 then i=n-1 is not valid position to apply operator.

We can go with any approach, for simplicity we will use #1 approach.

Handle zero

  // do not generate composite for 0 to skip 0xyz except the first one
  if (num[i] === '0' && j !== i) {
      continue;
  }

Evaluate expression using infix

Since generated expressions are infix operators therefore we can apply infix expression evaluation algorithm to calculate the ans.

For this problem, this approach will repeat evaluating same partial again and again therefore not suitable. For example 1+2+3+4+5+6 and 1+2+3+4+5-6 has common 1+2+3+4+5 therefore no need to recalculate every time.

Evaluate expression on the fly

Expression evaluation is based on the fly calculation as below.

    switch(operator) {
        case '+':
            evaluated = evaluated + operandInt;
            prevOperand = operandInt;
            break;
        case '-':
            evaluated = evaluated - operandInt;
            prevOperand = -operandInt;
            break;
        case '*':
            evaluated = evaluated - prevOperand + prevOperand * operandInt;
            prevOperand = prevOperand * operandInt;
            break;
        case '/':
            const t = Math.trunc(prevOperand / operandInt);
            evaluated = evaluated - prevOperand + t;
            prevOperand = t;
            break;
        default:                                                
    }

It means we can update recursion method as below.

f(i, slate, prevOperand, evaluated) = Generate expressions nums[i,..n-1]

Following is code to solve this problem.

/**
 * @param {string} num
 * @param {number} target
 * @return {string[]}
 */
var addOperators = function (num, target) {
    const n = num.length;
    const results = [];
    const recursion = (i, slate, prevOperand, evaluated) => { // process from i ....to n-1
        // base case
        if (i === n) {
            if (evaluated === target) {
                results.push(slate);
            }
            return;
        }
        // Generate all possible composite number
        for (let j = i; j < n; j++) {
            const str = num.substring(i, j + 1);
            const intVal = parseInt(str, 10);

            // do not generate composite for 0 to skip 0xyz except the first one
            if (num[i] === '0' && j !== i) {
                continue;
            }

            // since unery operator is not valid operation therefore handle i=0 separately
            if (i === 0) {
                recursion(j + 1, str, intVal, intVal);
            } else {
                // Apply all possible operator
                recursion(j + 1, slate + '+' + str, intVal, evaluated + intVal);
                recursion(j + 1, slate + '-' + str, -intVal, evaluated - intVal);
                recursion(j + 1, slate + '*' + str, prevOperand * intVal, (evaluated - prevOperand) + prevOperand * intVal);
            }

        }
    }
    recursion(0, '', 0, 0);
    return results;
};

Happy coding :-)