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. 由于只剩下加减运算符了，按顺序计算出结果即可。
实现代码：
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<char>();
var stackNum = new Stack<int>();
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<int>(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));
}
}