首页 > 代码库 > Basic Calculator II

Basic Calculator II

    该题和前面的"

Basic Calculator

"的处理方法一样,仅仅是增加了对"*"、"/"两种运算的支持。

class Solution {
public:
    bool isnum(char c){
        if(c >= '0' && c <= '9')
            return true;
        return false;
    }
    int calculate(string s) {        
        vector<string> postorder;
        stack<char> ccache;
        stack<int> icache;
        string tmp;
        if(s.length() < 1)
            return 0;
//构造后缀表达式
        for(int i = 0; i < s.length(); ){
            if(s[i] == ' '){
                i++;
                continue;
            }
            if(!isnum(s[i])){
                if(s[i] == '(' || ccache.empty()){
                    ccache.push(s[i]);
                    i++;
                    continue;
                }
                if(s[i] == ')'){
                    while(ccache.top() != '('){
                        tmp = "";
                        tmp += ccache.top();
                        postorder.push_back(tmp);
                        ccache.pop();
                    }
                    ccache.pop();
                    i++;
                    continue;
                }
                if(s[i] == '+' || s[i] == '-'){
                    while(!ccache.empty() && ccache.top() != '(' ){
                        tmp = "";
                        tmp += ccache.top();
                        postorder.push_back(tmp);
                        ccache.pop();
                    }
                    ccache.push(s[i]);
                    i++;
                    continue;
                }
                if(s[i] == '*' || s[i] == '/'){
                    while(!ccache.empty() && ccache.top() != '(' && ccache.top() != '+' && ccache.top() != '-'){
                        tmp = "";
                        tmp += ccache.top();
                        postorder.push_back(tmp);
                        ccache.pop();
                    }
                    ccache.push(s[i]);
                    i++;
                    continue;
                }
            }else{
                int j = i;
                while(j < s.length() && isnum(s[j]))
                    j++;
                tmp = "";
                tmp = s.substr(i, j - i);
                postorder.push_back(tmp);
                i = j;
            }
        }
//加入全部剩余的元素
        while(!ccache.empty()){
            tmp = "";
            tmp += ccache.top();
            ccache.pop();
            postorder.push_back(tmp);
        }
//通过后缀表达式计算结果值
            int fir, sec, result;
            for(int i = 0; i < postorder.size(); i++){
                if(postorder[i] == "+" || postorder[i] == "-" || postorder[i] == "*" || postorder[i] == "/"){
                    sec = icache.top();
                    icache.pop();
                    fir = icache.top();
                    icache.pop();
                    
                    if(postorder[i] == "+")
                        result = fir + sec;
                    if(postorder[i] == "-")
                        result = fir - sec;
                    if(postorder[i] == "*")
                        result = fir * sec;
                    if(postorder[i] == "/")
                        result = fir / sec;
                    
                    icache.push(result);
                }else{
                    icache.push(atoi(postorder[i].c_str()));
                }
            }
            return icache.top();
    }
};


Basic Calculator II