leetcode 224. Basic Calculator

女爷i 2022-07-28 05:24 167阅读 0赞

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.

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 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;
    		return cal_parenthes(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)
    				{
    					if (s[pos1 - 1] == '-')
    					{
    						s.erase(s.begin() + pos1 - 1, s.begin() + pos + 1);
    						s.insert(s.begin() + pos1 - 1, ss.begin(), ss.end());
    						s[pos1 - 1] = '+';
    					}
    					else
    					{
    						s.erase(s.begin() + pos1 - 1, s.begin() + pos + 1);
    						s.insert(s.begin() + pos1 - 1, 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