LeetCode -- Basic Calculator II

LeetCode -- Basic Calculator II

題目描述：


Implement a basic calculator to evaluate a simple expression string.


The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.


You may assume that the given expression is always valid.


Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5


就是對1個表達式解析出操作數和操作符，做四則運算，但不包括括號。


思路：
1. 去除空白字符
2. 考慮多位數字的情況
3. 如果是'*'或'/'，直接計算；否則入棧
4. 由於只剩下加減運算符了，按順序計算出結果即可。




實現代碼：

public int Calculate(string s)
{
	var exp = s.Where(c => c != ' ').ToList();
	
	var stackOp = new Stack();
	var stackNum = new Stack();
	
	var ops = new []{'+','-','*','/'};
	
	var n = "";
	for(var i = 0;i < exp.Count; i++){
		if(ops.Contains(exp[i])) // detected operator
		{
			stackOp.Push(exp[i]);
		}
		else{
			// parse the number
			for(var j = i;j < exp.Count; j++){
				if(!ops.Contains(exp[j])){
					n += exp[j];
				}
				else{
					break;
				}
			}
			
			var n1 = int.Parse(n);
			// if top is '*' or '/' , immediately calculate
			if(stackOp.Count > 0 && (stackOp.Peek() == '*' || stackOp.Peek() == '/')){
				var n2 = stackNum.Pop();
				stackNum.Push(Calc(n2, n1, stackOp.Pop()));
			}
			else{
				stackNum.Push(n1);
			}
			
			i += n.Length - 1;
			n = "";
		}
	}
	
	// since now we only left '+' and '-'
	// we should reverse the order (both operators and numbers) back to where they were
	var stackOp1 = stackOp.Reverse();
	var stackNum1 = new Stack(stackNum);
	var count = 0;
	
	foreach(var op in stackOp1){
		var n1 = stackNum1.Pop();
		var n2 = stackNum1.Pop();
		
		stackNum1.Push(Calc(n1 , n2, op));
		count += 2;
	}
	
	return stackNum1.Pop();
}


private int Calc(int n1 , int n2, char op)
{
	switch(op){
		case '+':
			return n1 + n2;
		case '-':
			return n1 - n2;
		case '*':
			return n1 * n2;
		case '/':
			return n1 / n2;
		default :
		throw new ArgumentException(string.Format("unexpected operator : {0}", op));
	}
}