題目描述：

    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 .

    You may assume that the given expression is always valid.

    Some examples:

    1 + 1 = 2

    2-1 + 2 = 3

    (1+(4+5+2)-3)+(6+8) = 23

    思路：

    1. 兩個(gè)棧，1個(gè)numStack存數(shù)字，1個(gè)opStack存(,),+,-

    2. 解析數(shù)字過程中，注意數(shù)字可能是多位數(shù)

    3. 如果是+,(,或-，直接入棧

    4. 如果是)，判斷當(dāng)前opStack最上操作符是否為'('，如果是直接彈出（標(biāo)記為彈出），如果opStack.Peek()不為'('且opStack中有元素，則進(jìn)行循環(huán)計(jì)算：

    4.1 opStack彈出1個(gè)，numStack彈出2個(gè)，計(jì)算結(jié)果入numStack

    4.2 最后判斷，如果最上層為'('且仍未彈出則彈出這個(gè)'('

    5.最后需要對(duì)余下opStack和numStack中的元素進(jìn)行計(jì)算，結(jié)果入numStack(與4.1過程一樣)

    最后彈出numStack的結(jié)果即可，

LeetCode Basic Caculator

    實(shí)現(xiàn)代碼：

public class Solution {public int Calculate(string s) {	// two stack	var pStack = new Stack<string>();	var numStack = new Stack<int>();	var n = ;	// if number , push number stack	for(var i = 0;i < s.Length; i++){		if(s[i] == ' '){			continue;		}				// if (, +,- , push op stack		if(s[i] == '(' || s[i] == '+' || s[i] == '-'){			opStack.Push(s[i].ToString());		}		// if ).  pop op stack, pop 2 from number stack, until reach '('		else if(s[i] == ')'){			var poped = false;			if(opStack.Count > 0 && opStack.Peek() == (){				poped = true;				opStack.Pop();			}						while(opStack.Count > 0 && opStack.Peek() != (){				var n1 = numStack.Pop();				var n2 = numStack.Pop();				var o = opStack.Pop();				numStack.Push(Calc(n1, n2, o));			}			if(!poped && opStack.Count > 0 && opStack.Peek() == (){				opStack.Pop();			}					}		// push num into numStack, try calc until reach '('		else		{			// parse out number 			var valid = 0123456789;			if(valid.Contains(s[i])){				n += s[i];				if(i == s.Length - 1 || !valid.Contains(s[i+1])){					numStack.Push(int.Parse(n));					n = ;					while(opStack.Count > 0 && opStack.Peek() != ()					{						var o = opStack.Pop();						var n1 = numStack.Pop();						var n2 = numStack.Pop();						numStack.Push(Calc(n1,n2,o));					}									}			}		}	}		// pop the rest ops in opstack and numbers in number stack		while(opStack.Count > 0){		var o = opStack.Pop();		if(o != + && o != -){			continue;		}		var n1 = numStack.Pop();		var n2 = numStack.Pop();		numStack.Push(Calc(n1,n2,o));	}		return numStack.Pop();}	public int Calc(int n1, int n2, string op){	switch(op)	{		case + :			return n1 + n2;		case - :			return n2 - n1;		default :		throw new NotSupportedException();	}}}</int></string>