Prompt: Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example:

Input: s = "3+2*2"
Output: 7

Input: s = " 3/2 "
Output: 1

Input: s = " 3+5 / 2 "
Output: 5

Solution: We have to calculate all the multiplication and division first and then addition and subtraction. We can use a temporary stack to solve this. We can loop through the string and evaluate each character. First, we can filter through all possible valid characters in the string. All possible valid characters in the string are integers from range 0 to 9 and the four operators.

In order to process all integers by individual characters, we can start with a current integer as 0 and update the current integer by multiplying it by 10 to shift it to the left one decimal place and add the current character’s integer value.

When we loop on an operator, we can deal with the current integer accordingly. If it’s an add operator, we can just add the current integer to the stack. If it’s a subtract operator, we can add the negative of the current integer to the stack. If it’s a multiply operator, we can update the last element in the stack by multiplying it by the current integer. If it’s a division operator, we can update the last element in the stack by dividing it with the current integer.

Finally, we can just sum all the elements in the stack and return the result. The runtime for this solution is O(n).