A C# solution without using stacks.


  • 0
    R

    No need to use stack, as we only need to go back at most one step thanks to the simplified requirements. We can do the calculation as we read through the input string. Only time we need to cache and wait is when the current operator is + or -, and the next operator is * or /. Then we need to cache the left operand and the operator, move the right operand to be the left operand, and continue to read the next number to calculate the * or / operation. Until we come to the next + or - operator, or end of string, we can come back to do the cached operation.

    (the codes are a bit verbose, but hope they are easier to read)

    public class Solution {
        public int Calculate(string s) {
                String curNumStr;
                char curChar;   //current char
                char curOp;     //current operator, if * or /, calculate now; if + or -, see nextOp;
                char nextOp;    //next operator
                char preOp;     //cached previous operator, if curOp is + or -, pop it out to calculate;
                int leftNum;    //number on the left of the current operator;
                int rightNum;   //number on the right of the current operator
                int preLeftNum; //cached previous number on the left of the previous operator
    
                //Set up initial value;
                curOp = ' ';
                curNumStr = "";
                leftNum = 0;
                rightNum = 0;
                preLeftNum = 0;
                preOp = ' ';
    
                //Read in char one by one
                for (int n = 0; n < s.Length; )
                {
                    curChar = s[n]; n++;    //read next char, increase counter
                    if ((curChar == ' ') && ( n < s.Length)) continue;  //skip white space, but not the last char
    
                    //if char is number, keep reading to get the whole number
                    while (Char.IsDigit(curChar))
                    {
                        curNumStr += curChar;
                        if (n == s.Length) break;   //reach end of the string, stop reading
                        else curChar = s[n]; n++;
                    }
                    if (curNumStr != "")
                    {
                        rightNum = Convert.ToInt32(curNumStr);  //done with reading the number string, convert the string to int
                        curNumStr = "";  //reset string for next number
                    }
    
                    if ((curChar == ' ') && (n < s.Length)) continue; //skip white space after the number
    
                    //we can assume the next char after a number is always an operator or end of string
                    nextOp = curChar; //if at end of string, curChar may not be a valid operator, but we wont use it 
    
                    //if current operator is blank, it means it's the first number we read, 
                    //move the number we read from right to left of the current operator
                    //and set the next operator to be the current operator
                    //in the other case, the number we read will be the number on the right of the current operator
                    if (curOp == ' ')
                    {
                        leftNum = rightNum;
                        curOp = nextOp;
                    }
                    else
                    {  //now we have left number, current operator, the right number, and the next operator after the right number
                        //'*' and '/' have highest priority, can calculate it now regardless what's next or before
                        //e.g. 2+3*5 => 2+15
                        if ((curOp == '*') || (curOp == '/'))
                        {
                            leftNum = doMath(leftNum, rightNum, curOp);
                            curOp = nextOp;  //right number merged into the left number, nextOp become the curOp
                        }
                        else
                        {
                            //if current operator is +/-, we can go back to do the previously cached +/- calculation
                            //e.g. 2+3-1 => 5-1
                            if (preOp != ' ') leftNum = doMath(preLeftNum, leftNum, preOp);
                            preOp = ' ';  //clear the preOp as it has been calculated
    
                            //now we need to look at the next operator, if it's * or /, then we need to cached the current left number and operator, 
                            //and move on to do the next * or / calculation first      
                            if ((nextOp == '*') || (nextOp == '/'))
                            {                   
                                preLeftNum = leftNum;
                                preOp = curOp;
                                leftNum = rightNum;
                                curOp = nextOp;
                            }
                            else  //else if it's + or -, or end of string, we can do the current + or - calculation
                            {
                                leftNum = doMath(leftNum, rightNum, curOp);
                                curOp = nextOp;
                            }
                        }
                    }
                }
    
                //at the end, need to finish the cached operation
                if (preOp != ' ') leftNum = doMath(preLeftNum, leftNum, preOp);
                return leftNum;
            }
    
            //help function to do the actual calculation
            public int doMath(int left, int right, char op)
            {
                //Console.WriteLine(left + Char.ToString(op) + right);
    
                switch (op)
                {
                    case '+': return left + right;
                    case '-': return left - right;
                    case '*': return left * right;
                    case '/': return left / right;
                    default: return right; // in the case of op is blank, return the right number
                }
            }    
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.