Amazon Interview Question
SDE1sCountry: United States
int EvaluateExpr(const std::string &postfix)
{
if (postfix.size()<1)
return 0;
std::array<char,4> oper={'+','-','*','/'};
std::stack<int> result;
for(auto ch:postfix)
{
auto ret= std::find_if(oper.cbegin(),oper.cend(),[ch](char ch1){ if (ch== ch1) return true;return false;});
if ( ret != oper.cend()) // so we find the operator
{
auto val1 = result.top();result.pop();
auto val2 = result.top();result.pop();
switch (ch)
{
case '+':result.push(val1+val2);
break;
case '-':result.push(val1-val2);
break;
case '*':result.push(val1*val2);
break;
case '%':result.push(val1/val2);
break;
default:
break;
}
}
else
{
int val = ch-'0';
result.push(val);
}
}
return result.top();
}
it can be work in java like this, it is in complete but we have to add more condition for diffrent operator
public class A6 {
public static void main(String[] args) {
String str="423+*";
Stack st=new Stack();
for(int i=0;i<str.length();i++)
{
char ch1=str.charAt(i);
if(ch1>=48 && ch1<=57)
{
int ch2 = ch1-48;
st.push(ch2);
}
else
{
switch(ch1)
{
case'+':
Integer x=(Integer)st.pop();
Integer y=(Integer)st.pop();
int z =x+y;
st.push(z);
break;
case '*':
Integer x1 =(Integer)st.pop();
Integer y1=(Integer)st.pop();
int z1=x1*y1;
st.push(z1);
break;
}
}
}
System.out.println(st.pop());
}
}
public int solvePostFix(String s)
{
Stack<Integer> values=new LinkedList<Integer>();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
values.push(Integer.parseInt(s.charAt(i));
}else
{
int sol=solveExprsn(values.pop().intValue(),values.pop().intValue(),s.charAt(i));
values.push(sol);
}
}
return values.pop().intValue();
}
private int solveExprsn(int first,int sec,char symbol)
{
switch (symbol){
case '+':
return first+sec;
case '*':
return first * sec;
case '-':
return first - sec;
case '/':
return first / sec;
default:
break;
}
return 0;
}
def isDigit(char):
if char >= '0' and char <= '9':
return True
else:
return False
def calculate(char1, char2, op):
if op == '+':
return char1 + char2
elif op == '-':
return char1 - char2
elif op == '*':
return char1 * char2
elif op == '/':
return char1 / char2
def postfix_calculator(str):
stack = []
for i in range(0, len(str)):
if isDigit(str[i]):
stack.append(int(str[i]))
else:
stack.append(calculate( stack.pop(), stack.pop(), str[i]))
return stack.pop()
print postfix_calculator("432+*")
import java.util.Stack;
public class AmazonPostFix {
@SuppressWarnings({ "unchecked", "rawtypes" })
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="423+*";
Stack <Integer>st=new Stack();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
String sts=""+s.charAt(i);
st.push(Integer.parseInt(sts));
}
else
{
int temp=0;
int a=(Integer)st.pop();
int b=(Integer)st.pop();
if(s.charAt(i)=='+')
temp=a+b;
else if(s.charAt(i)=='-')
temp=a-b;
if(s.charAt(i)=='*')
temp=a*b;
if(s.charAt(i)=='/')
temp=a/b;
st.push(temp);
}
}
System.out.println(st.pop());
}
}
import java.util.Stack;
public class AmazonPostFix {
@SuppressWarnings({ "unchecked", "rawtypes" })
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="423+*";
Stack <Integer>st=new Stack();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
String sts=""+s.charAt(i);
st.push(Integer.parseInt(sts));
}
else
{
int temp=0;
int a=(Integer)st.pop();
int b=(Integer)st.pop();
if(s.charAt(i)=='+')
temp=a+b;
else if(s.charAt(i)=='-')
temp=a-b;
if(s.charAt(i)=='*')
temp=a*b;
if(s.charAt(i)=='/')
temp=a/b;
st.push(temp);
}
}
System.out.println(st.pop());
}
}
class Solution {
public static void main(String[] args){
String s = "423+*";
System.out.println(evaluateExpr(s));
}
public static int evaluateExpr(String s){
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<s.length(); i++){
char c = s.charAt(i);
if(c == '+' || c == '-' || c == '*' || c == '/'){
int a = stack.pop();
int b = stack.pop();
int output = calculate(a, b, c);
stack.push(output);
} else{
stack.push(Character.getNumericValue(c));
}
}
return stack.pop();
}
public static int calculate(int a, int b, char operator){
int output = 0;
switch(operator){
case '+' :
output = a + b;
break;
case '-' :
output = b - a;
break;
case '*' :
output = a * b;
break;
case '/' :
output = b / a;
break;
}
return output;
}
}
class Solution {
public static void main(String[] args){
String s = "423+*";
System.out.println(evaluateExpr(s));
}
public static int evaluateExpr(String s){
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<s.length(); i++){
char c = s.charAt(i);
if(c == '+' || c == '-' || c == '*' || c == '/'){
int a = stack.pop();
int b = stack.pop();
int output = calculate(a, b, c);
stack.push(output);
} else{
stack.push(Character.getNumericValue(c));
}
}
return stack.pop();
}
public static int calculate(int a, int b, char operator){
int output = 0;
switch(operator){
case '+' :
output = a + b;
break;
case '-' :
output = b - a;
break;
case '*' :
output = a * b;
break;
case '/' :
output = b / a;
break;
}
return output;
}
}
this is a rather simple question, the length of the string is always odd, because for n operands there should be n-1 operators. in the give example of 423+* we can see that for 3 operands we have 2 operators that is true for all the cases. Now we know that the operands start from (n/2)+1. so iterate every i,i+1 with the operator at i+(n/2)-1.
Use stack to solve this problem.
- Susheel September 05, 20151. Insert the numbers first
2. When encounter an operand... Pop first 2 number and apply the operand
3. Insert the result back in to the stack
4. Continue with insertion of original character array