Calculator - Amazon Top Interview Questions

                        Solution in C++ :

int cmp(char a, char b) {
    int aa = (a == '+' || a == '-') ? 1 : 2;
    int bb = (b == '+' || b == '-') ? 1 : 2;
    return aa - bb;
}

int calc(stack<int>& sk, stack<char>& op) {
    int b = sk.top();
    sk.pop();
    int a = sk.top();
    sk.pop();
    char c = op.top();
    op.pop();
    if (c == '+') return a + b;
    if (c == '-') return a - b;
    if (c == '*') return a * b;
    if (c == '/') return (int)floor(1.0 * a / b);
    assert(false);
    return 0;
}

int solve(string s) {
    stack<int> sk;
    stack<char> op;
    for (int i = 0, j = 0; j < s.size();) {
        if (s[j] == '-') j++;
        while (j < s.size() && isdigit(s[j])) j++;
        int n = stoi(s.substr(i, j - i));
        sk.push(n);
        if (j == s.size()) {
            while (!op.empty()) sk.push(calc(sk, op));
            break;
        } else {
            if (op.empty() || cmp(s[j], op.top()) > 0) {
                op.push(s[j]);
            } else {
                while (!op.empty() && cmp(s[j], op.top()) <= 0) {
                    sk.push(calc(sk, op));
                }
                op.push(s[j]);
            }
        }
        j++;
        i = j;
    }
    return sk.top();
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    private String str;
    private int idx = 0;
    public int solve(String s) {
        if (s == null || s.length() == 0)
            return 0;
        s = "+" + s.trim();
        List<Character> ops = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        str = s;
        idx = 0;
        String word = null;
        while ((word = getToken()) != null) {
            final char op = word.charAt(0);
            String op2 = getToken();
            int val = -1;
            if (Character.isDigit(op2.charAt(0))) {
                val = Integer.parseInt(op2);
            } else {
                val = Integer.parseInt(getToken());
                if (op2.charAt(0) == '-')
                    val = -val;
            }
            switch (op) {
                case '+':
                    ops.add(op);
                    list.add(val);
                    break;
                case '-':
                    ops.add(op);
                    list.add(val);
                    break;
                case '*':
                    list.set(list.size() - 1, list.get(list.size() - 1) * val);
                    break;
                case '/':
                    double denominator = list.get(list.size() - 1);
                    denominator /= val;
                    list.set(list.size() - 1, (int) Math.floor(denominator));
                    break;
            }
        }
        int res = 0;
        for (int i = 0; i != list.size(); i++) {
            char op = ops.get(i);
            int val = list.get(i);
            res += (op == '+' ? val : -val);
        }
        return res;
    }

    private String getToken() {
        while (idx != str.length()) {
            if (str.charAt(idx) == ' ') {
                idx++;
                continue;
            } else {
                if (Character.isDigit(str.charAt(idx))) {
                    int j = idx;
                    while (j + 1 != str.length() && Character.isDigit(str.charAt(j + 1))) j++;
                    String res = str.substring(idx, j + 1);
                    idx = j + 1;
                    return res;
                } else {
                    return str.substring(idx, ++idx);
                }
            }
        }
        return null;
    }
}
                    

                        Solution in Python : 
                            
def inorder(s):
    infix = []
    operand = ""
    prev_operator = "+"
    for c in s:
        if c not in "+-*/":
            operand += c
        elif prev_operator in "+-*/" and c == "-":
            # negative number found!
            operand += c
        else:
            infix.append(operand)
            infix.append(c)
            operand = ""
        prev_operator = c
    infix.append(operand)
    return infix


# convert infix to postfix expression using a stack
def postorder(s):
    # ops stack is storing the operators
    ops = []
    res = []

    for c in s:
        if c not in "+-/*":
            res.append(int(c))
        elif c in "/*" and len(ops) and ops[-1] in "+-" or len(ops) == 0:
            ops.append(c)
        else:
            # while precedence of operator is greater than or equal
            while len(ops) and (ops[-1] in "*/" or c in "+-"):
                res.append(ops.pop())
            ops.append(c)

    while len(ops):
        res.append(ops.pop())

    return res


# postfix is easy to evaluate for CPU and easy to code for us!
def postorder_eval(postfix):
    res = []

    for c in postfix:
        if isinstance(c, str):
            b = int(res.pop())
            a = int(res.pop())
            if c == "+":
                c = a + b
            elif c == "-":
                c = a - b
            elif c == "*":
                c = a * b
            elif c == "/":
                c = a // b
            res.append(c)
        else:
            res.append(c)

    return res[-1]


class Solution:
    def solve(self, s):

        infix = inorder(s)
        print(infix)

        postfix = postorder(infix)
        print(postfix)

        return postorder_eval(postfix)