Given a string s representing a valid arithmetic expression, implement a basic calculator that evaluates the expression and returns its result as an integer. The string may contain digits, plus signs ‘+’, minus signs ‘-’, parentheses ‘(’, ‘)’, and spaces. You are not allowed to use Stack or any built-in methods that directly evaluate a string as a mathematical expression, such as eval() . Expressions may include nested parentheses and subtraction as a unary operator, for example “-3” or “-(2 + 1)”. A plus sign is never used as a unary operator, so you will never see “+1” or “+(2 + 3)”. There will never be two operators in a row. For example, if s = “1 + 1”, the output should be 2. If s = “ 2-1 + 2 “, the output should be 3. If s = “(1+(4+5+2)-3)+(6+8)”, the output should be 23. The input string is guaranteed to be a valid expression and will contain at least one digit. Its length can be up to 300000 characters.