## Epic Systems Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

Usually with this, we'd use the shunting yard algorithm to evaluate this with order of operations- convert to RPN then use 2 stacks. Since order of ops is being ignored here, this makes our lives a lot easier.

Keep one stack for numbers and another for operators. Start from the end of the string, pushing numbers on top of the number stack and operators on top of the operator stack.

Now that every number is pushed on the number stack and every operator is pushed on the operator stack we begin.
With whatever operator is on top of the operator stack, pop the top number, use the operator on the popped number and the currently top of the number stack number, then place this resulting number on top of the number stack. Pop the operator from the operator stack.

Repeat this process until there is one number on the number stack and no operators on the operator stack. If this isn't the result, then the string is invalid.

Comment hidden because of low score. Click to expand.
0

There is no need to overcomplicate things with stacks.
At any given point in time, you have at most the following:
- Previous result
- Operator
So just store each in a single variable and update them as you parse the input string.
The only work you need to do is when a number is encountered, see if an operator has been defined. If so, calculate [previous result] [operator] [number], set this to previous result and clear the operator.

Comment hidden because of low score. Click to expand.
2

It may seem like it's overcomplicating things at first, but the standard way of doing these kinds of problems involve the stack method as it gives a better range of possibilities if we want to expand the problem to take into account, for instance, order of ops, or even parenthetical expressions.

Your solution is definitely more simple, be more space efficient, and just as correct, don't get me wrong, but the stack method gives us more to discuss with a potential interviewer and serves as a good model to understand for a lot of problems similar to this (see checking balanced parentheses problem for example).

Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.Stack;

public class OperatorEvaluation {

public static void main(String[] args) {
// TODO Auto-generated method stub

Stack<String> OpStack = new Stack();
Stack<Integer> NumStack = new Stack();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+4*6-9";

StringBuffer sb = new StringBuffer(test);

char[] chars = (sb.reverse()).toString().toCharArray();

for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}

else
{
NumStack.push(Integer.parseInt(Character.toString(chars[i])));
}

}

while(!OpStack.isEmpty() )
{
String op = OpStack.pop();
char c = op.charAt(0);

int a = NumStack.pop();
int b = NumStack.pop();

if(c == '*')

result = a*b;

if(c== '+')

result = (a+b);

if(c == '-')

result = (a-b);

NumStack.push(result);

}
System.out.println(result);

}

}

Comment hidden because of low score. Click to expand.
0

Thank you, Shriram! The codes are pretty good. if test ="13+4*6-9",it'll be a problem. "13" are two chars. how to solve this problem? Thanks.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````import java.util.Stack;

public class OperatorEvaluation {

public static void main(String[] args) {
// TODO Auto-generated method stub

Stack<String> OpStack = new Stack<String>();
Stack<Integer> NumStack = new Stack<Integer>();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+41*6-9*4";

StringBuffer sb = new StringBuffer(test);

char[] chars = (sb.reverse()).toString().toCharArray();

for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}

else if(Character.isDigit(chars[i]))
{
String number = "";
int pushnumber;
while(Character.isDigit(chars[i]))
{
number += chars[i];

i++;

if( i > chars.length-1)
break;
}

StringBuffer buffer = new StringBuffer(number);
String push = (buffer.reverse()).toString();
pushnumber = Integer.parseInt(push);

NumStack.push(pushnumber);
i--;
}

else
break;

}

while(!OpStack.isEmpty()  )
{
String op = OpStack.pop();
char c = op.charAt(0);

int a = NumStack.pop();
int b = NumStack.pop();

if(c == '*')

result =  a*b;

if(c== '+')

result = (a+b);

if(c == '-')

result = (a-b);

NumStack.push(result);

}
System.out.println(result);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It should give compile time error.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Stack;

public class OperatorEvaluation {

public static void main(String[] args) {
// TODO Auto-generated method stub

Stack<String> OpStack = new Stack();
Stack<Integer> NumStack = new Stack();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+4*6-9";

StringBuffer sb = new StringBuffer(test);

char[] chars = (sb.reverse()).toString().toCharArray();

for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}

else
{
NumStack.push(Integer.parseInt(Character.toString(chars[i])));
}

}

while(!OpStack.isEmpty()  )
{
String op = OpStack.pop();
char c = op.charAt(0);

int a = NumStack.pop();
int b = NumStack.pop();

if(c == '*')

result =  a*b;

if(c== '+')

result = (a+b);

if(c == '-')

result = (a-b);

NumStack.push(result);

}
System.out.println(result);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the order of operations is just left to right we can just keep a running left to right total.

``````// Assumes a null terminated input string, integers values, and valid expression
int EvaluateString(char* inputString)
{
int currentTotal = GetNumber(inputString);

while (*inputString != '\0')
{
switch (*inputString)
{
case '*':
currentTotal *= GetNumber(++inputString);
break;

case '-':
currentTotal -= GetNumber(++inputString);
break;

case '+':
currentTotal += GetNumber(++inputString);
break;

default:
inputString++;
break;
}
}

return currentTotal;
}

int GetNumber(char* &inputString)
{
int currentNumber = 0;
int isPositive = 1;

if (*inputString == '-')
{
isPositive = -1;
inputString++;
}

while (*inputString >= '0' && *inputString <= '9')
{
// Multiply our current number by 10 and add the current parsed number
currentNumber = (currentNumber * 10) + (*inputString - '0');
inputString++;
}

return currentNumber * isPositive;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;

public class Solution {
ArrayList<Integer> numStack = new ArrayList<Integer>();
ArrayList<Character> opStack = new ArrayList<Character>();
public void stackify(String str)
{
for(int i=0;i<str.length();i++)
{
String s = "";
if(str.charAt(i)>='0' &&str.charAt(i)<='9')
{
while(i < str.length() && str.charAt(i)>='0' && str.charAt(i)<='9')
{
s=s+str.charAt(i);
i++;
}
i--;
}
if(str.charAt(i)=='+' || str.charAt(i)=='-' || str.charAt(i)=='*'||str.charAt(i)=='/')
{
}

}
}
public int evaluateString(String str)
{
stackify(str);
for(int i=0;i<opStack.size();i++)
{
int a = numStack.remove(0);
int b = numStack.remove(0);
int result=0;
char oper = opStack.get(i);
switch(oper)
{
case '+':result=a+b;
break;
case '-':result=a-b;
break;
case '*':result=a*b;
break;
case '/':result=a/b;
break;
}
}
return numStack.get(0);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String str = "34+4*6-9";
System.out.println(sol.evaluateString(str));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;

public class Solution {
ArrayList<Integer> numStack = new ArrayList<Integer>();
ArrayList<Character> opStack = new ArrayList<Character>();
public void stackify(String str)
{
for(int i=0;i<str.length();i++)
{
String s = "";
if(str.charAt(i)>='0' &&str.charAt(i)<='9')
{
while(i < str.length() && str.charAt(i)>='0' && str.charAt(i)<='9')
{
s=s+str.charAt(i);
i++;
}
i--;
}
if(str.charAt(i)=='+' || str.charAt(i)=='-' || str.charAt(i)=='*'||str.charAt(i)=='/')
{
}

}
}
public int evaluateString(String str)
{
stackify(str);
for(int i=0;i<opStack.size();i++)
{
int a = numStack.remove(0);
int b = numStack.remove(0);
int result=0;
char oper = opStack.get(i);
switch(oper)
{
case '+':result=a+b;
break;
case '-':result=a-b;
break;
case '*':result=a*b;
break;
case '/':result=a/b;
break;
}
}
return numStack.get(0);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String str = "34+4*6-9";
System.out.println(sol.evaluateString(str));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple program with O(1) memory requirement.

``````#include <iostream>
#include<string>
#include<cctype>
using namespace std;

int evaluate(char oper , int leftOp,int rightOp){
cout<<"Evaluate "<<leftOp<<" "<<oper<<" "<<rightOp<<endl;
int result;
switch(oper){
case '*' : result = leftOp * rightOp;
break;
case '+' : result = leftOp + rightOp;
break;
case '-' : result = leftOp - rightOp;
break;
}
return result;
}

int main() {
string expression = "3 * 4 + 8 -  9";

int leftOp , rightOp;
char oper ;

int i=0,k;
while((isdigit(expression[i]) or expression[i] == ' ') and i < expression.length())
i++;

leftOp = atoi(expression.substr(0,i).c_str());

while(i<expression.length())
{
k=i;
if(isdigit(expression[i]) or expression[i] == ' ' )
{
k = i;
while((isdigit(expression[k]) or expression[k] == ' ') and k < expression.length())
k++;

rightOp = atoi(expression.substr(i,k-i).c_str());

leftOp = evaluate(oper,leftOp,rightOp);
i = k-1;
}
else
oper = expression[i];
i++;
}
cout<<"Result = "<<leftOp<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple program with O(1) space complexity

``````#include <iostream>
#include<string>
#include<cctype>
using namespace std;

int evaluate(char oper , int leftOp,int rightOp){
cout<<"Evaluate "<<leftOp<<" "<<oper<<" "<<rightOp<<endl;
int result;
switch(oper){
case '*' : result = leftOp * rightOp;
break;
case '+' : result = leftOp + rightOp;
break;
case '-' : result = leftOp - rightOp;
break;
}
return result;
}

int main() {
string expression = "3 * 4 + 8 -  9";

int leftOp , rightOp;
char oper ;

int i=0,k;
while((isdigit(expression[i]) or expression[i] == ' ') and i < expression.length())
i++;

leftOp = atoi(expression.substr(0,i).c_str());

while(i<expression.length())
{
k=i;
if(isdigit(expression[i]) or expression[i] == ' ' )
{
k = i;
while((isdigit(expression[k]) or expression[k] == ' ') and k < expression.length())
k++;

rightOp = atoi(expression.substr(i,k-i).c_str());

leftOp = evaluate(oper,leftOp,rightOp);
i = k-1;
}
else
oper = expression[i];
i++;
}
cout<<"Result = "<<leftOp<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Stack;

public class OperatorEvaluation {

public static void main(String[] args) {
// TODO Auto-generated method stub

Stack<String> OpStack = new Stack<String>();
Stack<Integer> NumStack = new Stack<Integer>();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+41*6-9*4";

StringBuffer sb = new StringBuffer(test);

char[] chars = (sb.reverse()).toString().toCharArray();

for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}

else if(Character.isDigit(chars[i]))
{
String number = "";
int pushnumber;
while(Character.isDigit(chars[i]))
{
number += chars[i];

i++;

if( i > chars.length-1)
break;
}

StringBuffer buffer = new StringBuffer(number);
String push = (buffer.reverse()).toString();
pushnumber = Integer.parseInt(push);

NumStack.push(pushnumber);
i--;
}

else
break;

}

while(!OpStack.isEmpty()  )
{
String op = OpStack.pop();
char c = op.charAt(0);

int a = NumStack.pop();
int b = NumStack.pop();

if(c == '*')

result =  a*b;

if(c== '+')

result = (a+b);

if(c == '-')

result = (a-b);

NumStack.push(result);

}
System.out.println(result);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.LinkedList;

public class EvaluateLeftToRight {

public static void main(String[] args) {
String expression = "3*4+5-9+6";
if(expression.length() == 0)
System.out.println("Empty String");
if(expression.length() == 1)
System.out.println(Integer.parseInt(expression));
splitExpression(expression); //method to split the input string into numbers and operators
int result = evaluateExpression(); //method to evaluate the expression
System.out.println(result);
}

public static void splitExpression(String expression) {
String number = "";
for(int i = 0; i < expression.length() - 1; i++) {
// Check if character is operator or digit, if it is a operator, add the operator to the queue
if(expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*')
// if the character is a digit
else {
number += expression.charAt(i);
//then check for the next character, if it is an operator, the number ends here
if(expression.charAt(i + 1) == '-' || expression.charAt(i + 1) == '+' || expression.charAt(i + 1) == '*') {
number = "";
}
}
}

int i = expression.length();

// The last position in the string is yet to be operated on
// Find the second last position, if it is an operator, then the character at last position is a single digit number
if(expression.charAt(i - 2) == '-' || expression.charAt(i - 2) == '+' || expression.charAt(i - 2) == '*')
// Else, the number might contain more than one digit
else {
number += expression.charAt(i - 1);
}
}

public static int evaluateExpression() {
int number1 = numQueue.poll();
while(!opQueue.isEmpty()) {
int number2 = numQueue.poll();
char operator = opQueue.poll().charAt(0);
switch(operator) {
case '+' : number1 = number1 + number2; break;
case '-' : number1 = number1 - number2; break;
case '*' : number1 = number1 * number2; break;
}
}
return number1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems that the above answers are making it more complicated than it should be. To check if it is strictly from left to right, we only need to pay attention to the location of the * operators. If we have any * operator after either a + or - operator, then it is not strictly from left to right because * has the privilege. With this being said, the code would be very simple.

A sample C++ code:

``````class ArithmeticCheck
{
string str_to_check;
public:
ArithmeticCheck(string str): str_to_check(str){}

bool getResult()
{
unsigned long L = str_to_check.length();
int i = 0;
char operator_;
int count_operators = 0;
int count_operators_not_multiply = 0;
int operator_last_index = 0;

while (i < L)
{
if(!isdigit(str_to_check[i]))
{
operator_ = str_to_check[i];
count_operators++;

// not true if starts or ends with an operator
if(i==0 || i==L-1)
{
return false;
}

// not true if two sequential operators
if(operator_last_index == i-1)
{
return false;
}

// not true if a * found after either a + or - operation
if( (count_operators>1) && (operator_=='*') && (count_operators_not_multiply>=1))
{
return false;
}

if(operator_ != '*')
{
count_operators_not_multiply++;
}

operator_last_index = i;
}
i++;
}
return true;
}
};

int main()
{
string str = "99*8*5*48*3";
ArithmeticCheck a(str);
cout << "The result: " << a.getResult() << endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test2 {

public static void main(String[] args)
{
String a = "3*4+8-9";

int l = a.length();

int counter =0 ;
int result=0;

while(counter<l)
{

if(counter==0)
{

String a1 = Character.toString((a.charAt(counter)));
int b1  = Integer.parseInt(a1);
counter++;

char b2  = a.charAt(counter);// operator
counter++;

String a2 = Character.toString((a.charAt(counter)));
int b3  = Integer.parseInt(a2);
counter++;

if(b2=='+') result  = b1+b3;
else if(b2=='*') result  = b1*b3;
else if(b2=='-') result  = b1-b3;
}

else{

char b2  = a.charAt(counter);// operator
counter++;

String a1 = Character.toString((a.charAt(counter)));
int b1  = Integer.parseInt(a1);
counter++;

if(b2=='+') result  = result+b1;
else if(b2=='*') result  = result*b1;
else if(b2=='-') result  = result-b1;
}

}

System.out.println(result);

}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

easy

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.