[LeetCode]Basic Calculator

題目：Basic Calculator

給定一個合法的運算表達式，該表達式中只包含數字、'+'、'-'、' '、'('、')'。

思路：

簡單思考不用看成加減兩種運算，直接看成加法，只不過由正負；

如何處理括號呢？因為只看成加法，括號會影響的是數值的正負，那么通過去括號運算法則來修改當前值的正負就可以了。

具體來說，保存括號前的正負，括號內的正負都要乘以保存的正負。

int LeetCode::calculate(string s){int result = 0;vector<int>sign(2, 1);//當前元素的正負,如果輸入是7-?可能會兩次pop_back，為了不去判斷是否為空for (size_t i = 0; i < s.size(); i++){if (s[i] >= '0'){//因為題目說只有數字、+、-、*、/、(、)、 這幾種字符，其他都比數字小int k = 0;while (i < s.length() && isdigit(s[i]))k = k * 10 + s[i++] - '0';k = k*sign.back();result += k;sign.pop_back();--i;//i退回來
        }else if (s[i] == ')'){sign.pop_back();}else if (s[i] != ' '){//如果是左括號，就將括號展開，需要乘以括號外面的符號，所以要乘以sign.back()sign.push_back(sign.back()*(s[i] == '-' ? -1 : 1));}}return result;
}

題目：Basic CalculatorII

給定一個合法的運算表達式，該表達式中只包含數字、'+'、'-'、' '、'/'、'*'。

和上面相比增加了乘除，去掉了括號。

思路：

有了乘除就有不同的運算優先級，這里通過每次將加減的結果加到最終結果里面，使每次*/運算的時候，cur會從零開始，這樣屏蔽了前面的運算結果過，從而避免的優先級的判斷

int LeetCode::calculate(string s){int result = 0,cur = 0;char op = '+';//默認當前運算符為加for (size_t i = 0; i < s.size(); ++i){if (isdigit(s[i])){//數字int k = 0;while (i < s.length() && isdigit(s[i]))k = k * 10 + s[i++] - '0';//計算數值switch (op){case '+':cur = cur + k;break;case '-':cur = cur - k;break;case '*':cur = cur * k;break;case '/':cur = cur / k;break;default:return -1;//表達式有誤
            }--i;}else if(s[i] != ' '){if (s[i] == '+' || s[i] == '-'){//加減運算符與順序無關，由于沒有括號，每次加減的值立即給resultresult += cur;cur = 0;}op = s[i];//遇到乘除的時候，cur總是從零開始的，所以前面的運算沒有影響
        }}return result + cur;
}

思路：

其實，考慮第一題的思路，可以將加減法去掉，從而避免判斷運算優先級，因為乘除的優先級是一樣的；加減變成數字的符號，這樣，每次就只用計算乘除；

int calculate(string s) {stack<int> myStack;char sign = '+';//保存運算符int res = 0, tmp = 0;for (unsigned int i = 0; i < s.size(); i++) {if (isdigit(s[i]))tmp = 10*tmp + s[i]-'0';//計算出數值if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) {if (sign == '-')myStack.push(-tmp);//減法變成負數else if (sign == '+')myStack.push(tmp);//加法變成正數else {int num;//乘除運算if (sign == '*' )num = myStack.top()*tmp;elsenum = myStack.top()/tmp;myStack.pop();//將參與的上一個數值出棧myStack.push(num);//運算結果入棧
            } sign = s[i];tmp = 0;}}while (!myStack.empty()) {//所有的結果加起來res += myStack.top();myStack.pop();}return res;
}

以上的方法都是根據題意而取巧，如果放開運算表達式的限制，算法就不能用了。

思路：

這里有正常的通過雙棧存儲數值和運算符，遇到左括號運算符或數值都入棧，遇到運算符就先判斷優先級，將要入棧的運算符優先級低于或等于棧頂的運算符就將棧頂的運算符出棧并計算數值，知道棧頂的運算符優先級較低；

優先級順序從高到低如下：）> * >= / > + >= - > (;加減的優先級是一樣的，但是棧頂的運算符優先級高于正在訪問的運算符優先級，即：正在訪問的'+'/'-' < 棧頂的'+'/'-'。

這樣就可以按照通常的運算習慣讓程序計算表達式的結果。

int LeetCode::calcu(stack<int>& num, stack<char>& sign){//運算符棧和數值棧出棧做運算if (num.empty())return -1;//表達式有誤int k = num.top();num.pop();//都是雙目運算符，還需要一個數if (num.empty())return -1;//表達式有誤int m = num.top();num.pop();char ch = sign.top();sign.pop();int result = 0;switch (ch){case '+':result = m + k;break;case '-':result = m - k;break;case '*':result = m * k;break;case '/':result = m / k;break;default:return -1;//表達式有誤
    }return result;
}int LeetCode::operatorPriority(char op1, char op2){//判斷優先級if (op1 == '(' || op2 == '(')return false;if (op1 == '+' || op1 == '-'){if (op2 == '*' || op2 == '/')return false;}return true;
}int LeetCode::calculate(string s){stack<int>num;//數字棧stack<char>op;//符號棧int i = 0;while (i < s.length()){if (isdigit(s[i])){//是數字//拼接數字int k = 0;while (i < s.length() && isdigit(s[i]))k = k*10 + s[i++] - '0';num.push(k);continue;}else if (s[i] == ')'){//是右括號if (op.empty())return -1;if (op.top() == '('){op.pop();}else{//符號棧出棧并計算，知道遇到左括號，或某個棧為空while (!op.empty() && op.top() != '('){num.push(calcu(num, op));}op.pop();}++i;}else if (!isspace(s[i])){//非空格符，這里認為是運算符或左括號//下一個運算符入棧前先計算棧頂的運算符while (!op.empty() && operatorPriority(op.top(),s[i]))num.push(calcu(num, op));op.push(s[i]);}++i;}while (!op.empty()){num.push(calcu(num,op));}return num.top();
}

?