LeetCode Hard Problem: Basic Calculator III

-
Problem is here: https://leetcode.com/problems/basic-calculator-iii/description/

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Now given the number of submissions and acceptances, this is definitely not a super trivial problem:


Now since I had some ExpressionEvaluation code hanging around, I reused the code with some few modifications:

  • Keep it to basic operations only
  • Remove spaces from the expression
  • Change the data type during the evaluation to BigInteger. That way you avoid over/underflow partial calculations. In the very end, cast the result back to Integer
And that's it! Code is down below, cheers, Marcelo


    public class Solution
    {
        public int Calculate(string s)
        {
            BigInteger retVal = 0;
            ExpressionEvaluation(RemoveSpaces(s), out retVal);
            return (int)retVal;
        }

        private string RemoveSpaces(string s)
        {
            if (String.IsNullOrEmpty(s)) return s;
            string retVal = "";
            for (int i = 0; i < s.Length; i++)
                if (s[i] != ' ') retVal += s[i].ToString();
            return retVal;
        }

        private bool ExpressionEvaluation(string expression,
                                          out BigInteger result)
        {
            result = 0;

            if (expression == null)
            {
                return false;
            }

            if (expression.Trim().Length == 0)
            {
                return true;
            }

            if (BigInteger.TryParse(expression, out result))
            {
                return true;
            }

            if (expression.Length > 2 &&
                expression.StartsWith("(") &&
                expression.EndsWith(")") &&
                IsWellFormedBrackets(expression.Substring(1, expression.Length - 2)))
            {
                return ExpressionEvaluation(expression.Substring(1, expression.Length - 2), out result);
            }

            char[] operators = new char[] { '+', '-', '*', '/' };
            foreach (char op in operators)
            {
                int bracketsCount = 0;
                for (int i = expression.Length - 1; i >= 0; i--)
                {
                    if (expression[i] == '(')
                    {
                        bracketsCount++;
                    }
                    else if (expression[i] == ')')
                    {
                        bracketsCount--;
                    }

                    if (expression[i] == op &&
                        bracketsCount == 0)
                    {
                        BigInteger value1 = 0;
                        BigInteger value2 = 0;
                        string part1 = "";
                        string part2 = "";

                        if (i > 0)
                        {
                            part1 = expression.Substring(0, i);
                        }
                        if (i + 1 < expression.Length)
                        {
                            part2 = expression.Substring(i + 1);
                        }
                        if (!ExpressionEvaluation(part1, out value1))
                        {
                            return false;
                        }
                        if (!ExpressionEvaluation(part2, out value2))
                        {
                            return false;
                        }

                        switch (op)
                        {
                            case '+':
                                result = value1 + value2;
                                break;
                            case '-':
                                result = value1 - value2;
                                break;
                            case '*':
                                result = value1 * value2;
                                break;
                            case '/':
                                if (value2 == 0)
                                {
                                    return false;
                                }
                                result = value1 / value2;
                                break;
                        }

                        return true;
                    }
                }
            }

            return false;
        }

        private static bool IsWellFormedBrackets(string expression)
        {
            if (expression == null ||
                expression.Trim().Length == 0)
            {
                return true;
            }

            int bracketsCount = 0;
            for (int i = 0; i < expression.Length; i++)
            {
                if (expression[i] == '(')
                {
                    bracketsCount++;
                }
                else if (expression[i] == ')')
                {
                    bracketsCount--;
                }
                if (bracketsCount < 0)
                {
                    return false;
                }
            }

            return bracketsCount == 0;
        }
    }

Comments

  1. TarasJanuary 29, 2018 at 10:49 AM

    very nice, Marcelo! I decided to use a different way of solving this problem by reducing it to a much simpler problem of evaluating an expression defined in postfix form. In order to do this, we just need to convert an infix form to a postfix form and fortunately Dijkstra, as always, invented an awesome algorithm to do just that and it's called shunting yard algorithm. What I like about this solution is that the problem is nicely split into 2 much simpler ones and it also works very well for evaluating expressions with variables, since we don't have to re-parse the entire expression every time in order to evaluate it. As always, my convoluted solution below:

    class Solution {
    private:
    int operator_precedence(char op) {
    if (op == '(') return 1;
    if (op == '+' || op == '-') return 2;
    return 3; // * or /
    }

    vector parse(const string& text) {
    stack operators;
    vector tokens;
    int i = 0;
    while (i < text.size()) {
    if (text[i] == ' ') {
    i += 1;
    } else if (text[i] == '(') {
    operators.push(text[i++]);
    } else if (text[i] == ')') {
    while (operators.top() != '(') {
    tokens.emplace_back(1, operators.top());
    operators.pop();
    }
    operators.pop();
    i += 1;
    } else if (isdigit(text[i])) {
    int start = i++;
    while (i < text.size() && isdigit(text[i])) { i += 1; }
    tokens.emplace_back(text.substr(start, i - start));
    } else {
    while (!operators.empty() && operator_precedence(operators.top()) >= operator_precedence(text[i])) {
    tokens.emplace_back(1, operators.top());
    operators.pop();
    }
    operators.push(text[i++]);
    }
    }
    while (!operators.empty()) {
    tokens.emplace_back(1, operators.top());
    operators.pop();
    }
    return tokens;
    }

    function to_function(char op) {
    switch (op) {
    case '+': return plus();
    case '-': return minus();
    case '/': return divides();
    case '*': return multiplies();
    }
    }

    long evaluate(const vector& tokens) {
    stack operands;
    for (const string& token: tokens) {
    if (isdigit(token.front())) {
    operands.push(stol(token));
    } else {
    auto func = to_function(token.front());
    long operand_2 = operands.top(); operands.pop();
    long operand_1 = operands.top(); operands.pop();
    operands.push(func(operand_1, operand_2));
    }
    }
    return operands.top();
    }
    public:
    int calculate(const string& text) {
    if (text.empty()) return 0;
    const auto& tokens = parse(text);
    return evaluate(tokens);
    }
    };

    Cheers,
    Taras

    ReplyDelete
    Replies
    1. AnonymousNovember 23, 2018 at 8:45 PM

      what (const string& text) even mean?

      Can't you just convert it to leetcode format? Thanks!
      public int Calculate(string s)
      {
      BigInteger retVal = 0;
      ExpressionEvaluation(RemoveSpaces(s), out retVal);
      return (int)retVal;
      }

      Delete
    2. TarasNovember 23, 2018 at 8:46 PM

      (const string& text) means that it's a C++ and it's in leetcode format ;)

      Delete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th
Read more