leetcode 227. Basic Calculator II

小咪咪 2022-07-28 05:27 132阅读 0赞

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, `+`, `-`, `*`, `/` operators and empty spaces ``. The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
    " 3/2 " = 1
    " 3+5 / 2 " = 5

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

class Solution {
    	int my_atoi(string &s)
    	{
    		int k = s[0] == '-' ? 1 : 0;
    		int re = 0;
    		while (k < s.length())
    		{
    			re = 10 * re + s[k] - '0';
    			k++;
    		}
    		return s[0] == '-' ? -re : re;
    	}
    	string my_itoa(int num)
    	{
    		if (num == 0)
    			return "0";
    		string s;
    		int n = abs(num);
    		while (n != 0)
    		{
    			s.insert(s.begin(), n % 10 + '0');
    			n /= 10;
    		}
    		if (num < 0)
    			s.insert(s.begin(), '-');
    		return s;
    	}
    	int cal_parenthes(string &s)
    	{
    		
    		int p1 = s.find('*');
    		int p2 = s.find('/');
    		while (p1 != string::npos || p2 != string::npos)
    		{
    			int pp;
    			if (p1 != string::npos && p2 != string::npos)
    				pp = p1 < p2 ? p1 : p2;
    			else if (p1 != string::npos)
    				pp = p1;
    			else
    				pp = p2;
    			int i1 = pp - 1;
    			while (i1 >= 0 && s[i1] - '0' >= 0 && s[i1] - '9' <= 0)
    				i1--;
    			i1++;
    			int n1 = my_atoi(string(s.begin() + i1, s.begin() + pp));
    			int i2 = pp + 1;
    			while (i2 < s.length() && s[i2] - '0' >= 0 && s[i2] - '9' <= 0)
    				i2++;
    			i2--;
    			int n2 = my_atoi(string(s.begin() + pp + 1, s.begin() + i2 + 1));
    			int rr = s[pp] == '*' ? n1*n2 : n1 / n2;
    			s.erase(s.begin() + i1, s.begin() + i2 + 1);
    			string dd = my_itoa(rr);
    			s.insert(s.begin() + i1, dd.begin(), dd.end());
    			p1 = s.find('*');
    			p2 = s.find('/');
    		}
    		while (true)
    		{
    			int starter = s[0] == '-' ? 1 : 0;
    			int k = starter + 1;
    
    			while (k < s.length() && (s[k] - '0' >= 0 && s[k] - '9' <= 0))
    				k++;
    			if (k == s.length())
    				return my_atoi(s);
    
    			int num1 = my_atoi(string(s.begin(), s.begin() + k));
    			int st2 = k + 1; k++;
    			while (k < s.length() && (s[k] - '0' >= 0 && s[k] - '9' <= 0))
    				k++;
    			int num2 = my_atoi(string(s.begin() + st2, s.begin() + k));
    			int re = s[st2 - 1] == '+' ? num1 + num2 : num1 - num2;
    			s.erase(s.begin(), s.begin() + k);
    			s = my_itoa(re) + s;
    		}
    
    	}
    public:
    	int calculate(string s) {
    		int p = s.find(' ');
    		while (p != string::npos)
    		{
    			s.erase(s.begin() + p, s.begin() + p + 1);
    			p = s.find(' ');
    		}
    		int pos = s.find(')');
    		while (pos != string::npos)
    		{
    			int pos1 = pos - 1;
    			while (s[pos1] != '(')
    				pos1--;
    			int re = cal_parenthes(string(s.begin() + pos1 + 1, s.begin() + pos));
    			string ss = my_itoa(re);
    			if (re < 0)
    			{
    				if (pos1 - 1 > 0)
    				{
    					int kk = pos1 - 1;
    					while (kk >= 0 && s[kk] != '+'&&s[kk] != '-')
    						kk--;
    					if (kk >= 0)
    					{
    						if (s[kk] == '-')
    						{
    							s.erase(s.begin() + pos1, s.begin() + pos + 1);
    							s.insert(pos1 ==s.length()?s.end():s.begin() + pos1 , ss.begin()+1, ss.end());
    							s[kk] = '+';
    						}
    						else
    						{
    							s.erase(s.begin() + pos1, s.begin() + pos + 1);
    							s.insert(pos1 == s.length() ? s.end() : s.begin() + pos1 , ss.begin()+1, ss.end());
    							s[kk] = '-';
    						}
    					}
    					else
    					{
    						s.erase(s.begin(), s.begin() + pos + 1);
    						s.insert(s.begin(), ss.begin(), ss.end());
    					}
    				}
    				else
    				{
    					s.erase(s.begin(), s.begin() + pos + 1);
    					s.insert(s.begin(), ss.begin(), ss.end());
    				}
    			}
    			else
    			{
    				s.erase(s.begin() + pos1, s.begin() + pos + 1);
    				s.insert(s.begin() + pos1, ss.begin(), ss.end());
    			}
    			pos = s.find(')');
    		}
    		return cal_parenthes(s);
    	}
    };

accepted