Basic Calculator - LeetCode 224

题目描述：

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

Note: Do not use the eval built-in library function.

Hide Tags Stack Math

分析：

该题要实现一个带有括号优先级的加减法计算器，实质就是栈的使用。不多说了，直接看代码注释吧

/**///56ms//*/
class Solution {
public:
    int docompute(int a,int b,char opd){ //计算a opera b
	if(opd == '+')
	    return a + b;
	if(opd == '-')
	    return a - b;		
	}
    bool isopd(char ch){ //判断是否是运算符
	return (ch == '+' || ch == '-' || ch == '(' || ch == ')'||ch == '=');
    }
    int calculate(string s) {
	int len = s.size();
	if(len == 0)
	    return 0;
	s.push_back('='); //在表达式末尾加上'='，方便判断是否计算结束		
        stack<char> opd;
	opd.push('='); //在运算符栈底添加'='，方便判断是否计算结束

	stack<int> num; //操作数栈
	int i = 0;
	while( i <= len){ 
	    if(isdigit(s[i])){ // 如果是数字字符，则转换为整数后压入操作数栈。注意处理多位数的情况
		int dat = 0;
	        while(isdigit(s[i])){
		    dat = dat * 10 + (s[i]-'0');
			i++;
		}				
		num.push(dat);				
	    }
	    else if(isopd(s[i])){ //如果是运算符 
		if(s[i] == '('){  '('直接压入栈
		    opd.push(s[i]);
		    i++;
		    continue;
		}
		if(s[i] == ')'){  
                //遇到')'时，需判断栈顶运算符是'+'或'-'，直接取出计算后将结果要入操作数栈；
                //否则只能是'('，弹出栈.
                //继续处理下一个字符
		    char oper = opd.top(); 
		    opd.pop();
		    if(oper == '+' || oper == '-'){
	                int a = 0, b = 0;
			b = num.top();
			num.pop();
			a = num.top();
			num.pop();
			int re = docompute(a,b,oper);
			num.push(re);					
			opd.pop(); //pop teh '('
		    }
		    i++; 
		    continue;
		}	
	        if(s[i] == '+' || s[i] == '-'){  //遇到'+'或‘-’，看运算符栈顶
		    char oper = opd.top(); 
		    if(oper == '=' || oper == '('){ //若运算符栈顶是'='或'('，直接将当前运算符压入栈
			opd.push(s[i]);
			i++;
			continue;
		    }
		    else{  //栈顶为'+'或'-',取出计算
			opd.pop();
			int a = 0, b = 0;
			b = num.top();
			num.pop();
			a = num.top();
			num.pop();
			int re = docompute(a,b,oper);
			num.push(re);
			continue;
		    }
		}
		if(s[i]=='='){ //遇到'='，
		    if(opd.top() == '=') //栈顶也是'='，表示计算结束，返回结果
			return num.top();
		    else{ //不是等于，表明还有运算符，且只能是'+'或'-',取出计算结果
			char oper = opd.top();
			opd.pop();
			int a = 0, b = 0;
			b = num.top();
		        num.pop();
			a = num.top();
			num.pop();
			int re = docompute(a,b,oper);
			//cout << re << endl;
			num.push(re);
			continue;
		    }
		}

            } 
	    else //跳过空格
		i++;
        }
		
    }
};