Problem: This problem is similar to our previous Calculator problem with difference here is the expression string contains only non-negative integers, +, -, *, / operators and empty spaces.
Example:
Input: " 4 *3+5 / 2 " Output: 14
Approach: We will take the same approach which we have taken in the previous problem. We will use the stack only. We just need to take care of precedence of operators here i.e. '*' and '/' are going to be executed first.
What we can do is we will keep push operands in stack, if there is a '-' operator we will push "-operand" to stack to take care of subtraction . If we see '*' or '/ ' operator then we apply the operation on top of stack and current number and will push the result to stack.
In the end we will add all the number in the stack and that will be our answer.
Implementation in C#:
public static int CalculateII(string s)
{
if (string.IsNullOrWhiteSpace(s))
{
return 0;
}
Stack<int> stack = new Stack<int>();
int operand = 0;
char operation = '+';
for (int i = 0; i < s.Length; ++i)
{
if (char.IsDigit(s[i]))
{
operand = operand * 10 + (s[i] - '0');
}
if ((!char.IsDigit(s[i]) && !char.IsWhiteSpace(s[i])) || i == s.Length - 1)
{
if (operation == '+')
{
stack.Push(operand);
}
else if (operation == '-')
{
stack.Push(-operand);
}
else if (operation == '*')
{
int operand1 = stack.Pop();
stack.Push(operand1 * operand);
}
else if (operation == '/')
{
int operand1 = stack.Pop();
stack.Push(operand1 / operand);
}
operation = s[i];
operand = 0;
}
}
int result = 0;
while (stack.Count > 0)
{
result += stack.Pop();
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment