# Calculator - Amazon Top Interview Questions

### Problem Statement :

```Given a string s representing a mathematical expression with"+", "-", "/", and "*", evaluate and return the result.

Note: "/" is integer division. Can you implement without using eval?

Example 1

Input

s = "1+2*4/6"

Output

2

Explanation

1 + ((2 * 4) / 6) = 2```

### Solution :

```                        ```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 '+':
break;
case '-':
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)```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty