Problem: 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.
Example:
Input: " (3-1) + 4 - 1" Output: 5
Approach: The problem description immediately gives hint of using stack. Given we need to evaluate sub expressions too because of parentheses so it looks like we have to delay our processing but if you see we just can't simply use stack as expression may contain '-' and subtraction is neither associative nor commutative i.e. A-B-C != C-B-A and (A-B) - C != A - (B - C).
If we look closely reading the string in reverse will easily solve our problem so here is our algorithm:
- Iterate the expression string in reverse order one character at a time. Since we are reading the expression character by character, we need to be careful when we are reading digits and non-digits.
- The operands could be formed by multiple characters. A string "123" would mean a numeric 123, which could be formed as: 123 >> 120 + 3 >> 100 + 20 + 3. Thus, if the character read is a digit we need to form the operand by multiplying a power of 10 to the current digit and adding it to the overall operand.
- Once we encounter a character which is not a digit, we push the operand onto the stack.
- When we encounter an opening parenthesis (, this means an expression just ended. (reading string in reverse). This calls for evaluation of the expression by popping operands and operators off the stack till we pop corresponding closing parenthesis. The final result of the expression is pushed back onto the stack.
- Push the other non-digits onto to the stack.
- Do this until we get the final result. It's possible that we don't have any more characters left to process but the stack is still non-empty. This would happen when the main expression is not enclosed by parenthesis. So, at the end, we can check if the stack is not empty. If it is, we treat the elements in it as one final expression and evaluate it the same way we would if we had encountered an opening bracket.
Implementation in C#:
public static int Calculate(string s)
{
if (string.IsNullOrWhiteSpace(s))
{
return 0;
}
Stack<Object> stack = new Stack<object>();
int operand = 0;
int pow = 0;
for (int i = s.Length - 1; i >= 0; --i)
{
if (char.IsDigit(s[i]))
{
operand += (int)Math.Pow(10, pow) * (int)(s[i] - '0');
++pow;
}
else if (s[i] != ' ')
{
if (pow > 0)
{
stack.Push(operand);
pow = 0;
operand = 0;
}
if (s[i] == '(')
{
int result = EvaluateExpression(stack);
stack.Pop();
stack.Push(result);
}
else
{
stack.Push(s[i]);
}
}
}
if (pow > 0)
{
stack.Push(operand);
}
return EvaluateExpression(stack);
}
private static int EvaluateExpression(Stack<Object> stack)
{
int result = 0;
if (stack.Count > 0)
{
result = (int)stack.Pop();
}
while (stack.Count > 0 && (char)stack.Peek() != ')')
{
char sign = (char)stack.Pop();
if (sign == '+')
{
result += (int)stack.Pop();
}
else
{
result -= (int)stack.Pop();
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment