[LeetCode] | Basic Calculator II

https://leetcode.com/problems/basic-calculator-ii/?tab=Solutions

思路1：Stack

开一个栈放整数，遇到加减号就压栈，遇到乘除号就取出栈顶与当前数做乘除再压回去。

基础操作：O(n)去掉字符串中的所有空格，取字符串的下一个整数。

Time complexity: O(n)
Space complexity: O(n)

class Solution { public:int calculate(string s) {if (s.empty()) return 0;// remove all the blanks in the strings.erase(remove(s.begin(), s.end(), ' '), s.end());stack<int> stk;string str = get_next(s, 0);stk.push(stoi(str));int i = str.size();while (i < s.size()) {char oper = s[i];string str = get_next(s, i + 1); // get the current numberint cur_num = stoi(str);if (oper == '+') {stk.push(cur_num);} else if (oper == '-') {stk.push(-cur_num);} else if (oper == '*') {int top = stk.top(); stk.pop();stk.push(top * cur_num);} else {int top = stk.top(); stk.pop();stk.push(top / cur_num);}i += (1 + str.size());}int ret = 0;while (!stk.empty()) {ret += stk.top();stk.pop();}return ret;}private:string get_next(string& s, int pos) {int end = pos;while (end < s.size() && isdigit(s[end])) {end++;}return s.substr(pos, end - pos);} };

思路2：用trick实现O(1)的space

/** author : TK* date : 2017-02-22* problem : LeetCode 227. Basic Calculator* tags : String* language: C++*/ // key points: x+y*z = [(x+y)-y]+y*z, which make it possible to realize O(1) space // Time complexity: O(n) // Space complexity: O(1) class Solution { public:int calculate(string s) {if (s.empty()) return 0;// remove all the blanks in the strings.erase(remove(s.begin(), s.end(), ' '), s.end());string str = get_next(s, 0); // get the first numberint prev = stoi(str), ret = prev;int i = str.size();while (i < s.size()) {char oper = s[i];string str = get_next(s, i + 1); // get the current numberint cur_num = stoi(str);if (oper == '+') {ret += cur_num;prev = cur_num;} else if (oper == '-') {ret -= cur_num;prev = -cur_num;} else if (oper == '*') {ret = (ret - prev) + prev * cur_num;prev *= cur_num;} else {ret = (ret - prev) + prev / cur_num;prev /= cur_num;}i += (1 + str.size());}return ret;}private:string get_next(string& s, int pos) {int end = pos;while (end < s.size() && isdigit(s[end])) {end++;}return s.substr(pos, end - pos);} };

提醒：写完以后提交却妥妥地超时，检查后发现get_next()函数中的参数s没加引用，这可就灾难了，因为不加引用会进行字符串的整体copy...