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<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 numberfor(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 calculateif(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 werevar 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));}}

坚守自己的原则,世界上的诱-惑很多,

LeetCode — Basic Calculator II

相关文章:

你感兴趣的文章:

标签云: