Evaluate String Expression

Here is the full interview question "Evaluate String Expression - Uber Coding Interview | ShowOffer" from Uber on ShowOffer.io:

Problem Statement: Given a string expression, evaluate the expression and return the result. The expression can contain numbers, addition (+), subtraction (-), multiplication (*), and division (/) operations. The expression can also contain parentheses to indicate the order of operations.

Examples:

1. Input: "3 + 4 - 1 * 3" Output: 4

2. Input: "2 * (3 + 3) / 2" Output: 5

3. Input: "(2 + 3) * 4 / 2" Output: 10

Constraints:

• The input expression will be a valid string containing only numbers, addition (+), subtraction (-), multiplication (*), division (/) operations, and parentheses.
• The numbers in the expression will be non-negative integers.
• The division operation will not result in a division by zero.

Hints:

1. Use a stack-based approach to evaluate the expression.
2. Handle the order of operations by considering the precedence of the operators.
3. Use a loop to iterate through the characters in the expression and process the numbers and operators accordingly.

Solution: To solve this problem, you can use a stack-based approach to evaluate the expression while considering the order of operations. Here's a high-level algorithm:

1. Initialize two stacks: one for numbers (numStack) and one for operators (opStack).
2. Iterate through the characters in the input expression.
3. When you encounter a number, push it onto the numStack.
4. When you encounter an operator, pop the top operator from the opStack if it has higher or equal precedence than the current operator, and apply the popped operator to the top two numbers from the numStack. Push the result back onto the numStack. Then, push the current operator onto the opStack.
5. When you encounter a left parenthesis, push it onto the opStack.
6. When you encounter a right parenthesis, pop operators from the opStack and apply them to the numbers from the numStack until you encounter a left parenthesis. Pop the left parenthesis from the opStack.
7. After iterating through the entire expression, pop any remaining operators from the opStack and apply them to the numbers from the numStack.
8. The final result will be the only number left in the numStack.

Here's a Python implementation of the algorithm:

`python def evaluate_expression(expression): def apply_operator(op, a, b): if op == '+': return a + b if op == '-': return a - b if op == '*': return a * b if op == '/': return a // b

def precedence(op):
    if op in ('+', '-'): return 1
    if op in ('*', '/'): return 2
    return 0

num_stack = []
op_stack = []
i = 0
while i < len(expression):
    if expression[i].isdigit():
        j = i
        while j < len(expression) and expression[j].isdigit():
            j += 1
        num_stack.append(int(expression[i:j]))
        i = j - 1
    elif expression[i] == ' ':
        i += 1
    elif expression[i] == '(':
        op_stack.append(expression[i])
        i += 1
    elif expression[i] == ')':
        while op_stack[-1] != '(':
            num_stack.append(apply_operator(op_stack.pop(), num_stack.pop(), num_stack.pop()))
        op_stack.pop()
        i += 1
    else:
        while (len(op_stack) > 0 and precedence(op_stack[-1]) >= precedence(expression[i])):
            num_stack.append(apply_operator(op_stack.pop(), num_stack.pop(), num_stack.pop()))
        op_stack.append(expression[i])
        i += 1

while len(op_stack) > 0:
    num_stack.append(apply_operator(op_stack.pop(), num_stack.pop(), num_stack.pop()))

return num_stack[-1]

`

This solution should be able to evaluate the given string expression and return the correct result.