Leetcode discuss: 224. Basic Calculator

June 23, 2022

Here is the link. 

C# | Quick learner | Stack | Design talk

June 23, 2022
Introduction
I like to learn how to solve this hard level algorithm using a stack. To be a quick learner, I like to learn how to write a C# solution in less than 30 minutes by studying other people's ideas and code first, and then write down my learning process.

Discuss post | Analysis | Sanketj
Basic idea:

(1) Ignore all spaces.
(2) If currently at a number, find the entire number. Numbers can be comprised of multiple digits and can be negative.
(3) Minus signs can negate a number but they can also affect parentheses as explained in (4), so they need to be taken in the context of what comes after them.
(4) Parentheses can be 'dropped' if we account for the signs that precede them. If an open parenthesis is preceded by a plus sign, the plus sign has no impact. However, if it is preceded by a minus sign, then to drop the parenthesis, we have flip the signs inside the parenthesis. Consider the following example: "8 - (4 - (5 - 3))". The result should be 6. Parentheses can be dropped as follows: 8 - (4 - (5 - 3)) = 8 - (4 - 5 + 3) = 8 - 4 + 5 - 3 = 6. One observation here is that the minus between the 5 and 3 got flipped twice, which left it as a minus sign. In other words, an even number of preceding minus signs has no impact, only an odd number of preceding minus signs causes flipping. Therefore, we keep track of whether we have a odd or even number of preceding minuses. Beyond this, as we encounter a close parenthesis, we have to know the impact of the sign immediately before its corresponding open parenthesis, so that calculations for outer parentheses continue to happen correctly. Hence, we also maintain a stack of signs, pushing to it when an open parenthesis is seen, and popping when a close parenthesis is seen.

Learn from two test cases | Debug and think in 15+ minutes
I tried to go through two test cases, and see how the calculation is completed.
test case 1: 8 - (4 - (5 - 3))
test case 2: -(2+3)

We only have + and - two arithmetic operations, multiplication and division are not included. So it is a working idea to use a variable currentNum to store all intermediate calculation result, no data structure needed.

A stack is designed called signStack, and then it is C# Stack, only open parenthesis is stored in stack, and it is stored as false or true for minusLastSeen variable. For example, test case -(2+3), the char '(' is stored as false in signStack, since minusLastSeen is true.

Consider the following example: "8 - (4 - (5 - 3))". The result should be 6. Parentheses can be dropped as follows: 8 - (4 - (5 - 3)) = 8 - (4 - 5 + 3) = 8 - 4 + 5 - 3 = 6.

The design is to drop all parentheses, just using even or odd count to determine value whenever a close parenthesis ')' is met.

else if (c == ')')
{
	if (!signStack.Pop())
    {
		evenNumberOfMinusesOnStack = !evenNumberOfMinusesOnStack;
    }
}

if the top of signStack has false value, then evenNumberOfMinusesOnStack go to opposite. One variable can help to track so many - or + sign.

The calculation is implemented in the following statement:

result += (evenNumberOfMinusesOnStack ? 1 : -1) * currentNum;

Hard level | Take more test cases to learn
I like to learn more by debugging with more test cases. It is better to learn one thing a time using a simple test case, and then figure out how to design a working calculator. My goal is to learn how to solve the problem using stack, and also find a simplified solution to take care of all we need in order to get correct answer.

A list of test cases to help me to go through:
case 3: -(-(-2))
Walk through the above test case, explain how to solve the calculation.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _224_basic_calculator
{
    class Program
    {
        static void Main(string[] args)
        {
            // 8 - (4 - (5 - 3))
            var result = Calculate("8 - (4 - (5 - 3))");
            var result2 = Calculate("-(2+3)");
			var result3 = Calculate("-(-(-2))");
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/basic-calculator/discuss/498939/Accepted-C-solution%3A-Easy-to-understand
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int Calculate(string s)
        {
            int result = 0;
            bool minusLastSeen = false;
            bool evenNumberOfMinusesOnStack = true;
            int currentNum = 0;
            var signStack = new Stack<bool>();

            for (int i = 0; i < s.Length; i++)
            {
                var c = s[i];

                // skip the space char
                if (c == ' ')
                {
                    continue;
                }

                if (char.IsDigit(c))
                {
                    currentNum *= 10;
                    currentNum += (currentNum < 0 ? -1 : 1) * (c - '0');

                    if (minusLastSeen)
                    {
                        currentNum *= -1;
                        minusLastSeen = false;
                    }
                }
                else  // non digit - (,),-,+
                {
                    result += (evenNumberOfMinusesOnStack ? 1 : -1) * currentNum;
                    currentNum = 0;
                    if (c == '-')
                    {
                        minusLastSeen = true;
                    }
                    else
                    {
                        if (c == '(')
                        {
                            if (minusLastSeen)
                            {
                                evenNumberOfMinusesOnStack = !evenNumberOfMinusesOnStack;
                                signStack.Push(false);
                            }
                            else
                            {
                                signStack.Push(true);
                            }
                        }
                        else if (c == ')')
                        {
                            if (!signStack.Pop())
                            {
                                evenNumberOfMinusesOnStack = !evenNumberOfMinusesOnStack;
                            }
                        }

                        minusLastSeen = false;
                    }
                }
            }

            result += currentNum;
            return result;
        }
    }
}