CareerCup

/*
 Solution approach
 Using a handmade LL(1) Parser without real lexical analysis, 
 so whitespaces must not occure in the input string and token
 recogniztion is primitive

 It's a bit an overkill since it doesn't make use of all the information 
 given by the interviewer one can assume there is a "shortcut" 

 however, I find it rather exotic to try to find a special solution for a 
 problem that fits so cleanly into a theory space well understood. 

 Interesting situation in an interview :-)
 
 --
 EBNF
 PROGRAM	= INT, NEWLINE, {EXPRLINE}
 EXPRLINE	= EXPR, NEWLINE
 EXPR		= EXPR OP1 TERM | TERM
 TERM		= TERM OP2 FACT | TERM
 FACT		= INT | '(' EXPR ')' 
 OP1		= '+' | '-' 
 OP2		= '*' | '/'
 INT		= ['-'] DIGITS
 DIGITS		= DIGIT {DIGIT}
 DIGIT		= '0' | '1' | '2' | '3' | ... | '9'
 NEWLINE	= '\n'

 EXPR  and TERM are not LL(1), so convert into LL1:
 EXPR		= TERM {OP1 TERM}
 TERM		= FACT {OP2 FACT}

 --
 NOTE: 
 - {x}: x repated n times, 0<=n
 - [y]: y occures 0 or 1 times
 */
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Parser
{
private:
	string _buffer;
	int _position;

public:
	Parser(string buffer) : _buffer(buffer), _position(0) {}

	vector<int> Parse()
	{
		vector<int> result;
		Program(result);
		return result;
	}

private:
	//Production: PROGRAM	= INT, NEWLINE, {EXPRLINE}
	void Program(vector<int>& res)
	{
		int count = 0;
		if (!Int(count)) throw "E1";
		if (count < 0) throw "E2";
		if (!NewLine()) throw "E3";
		for (int i = 0; i < count; i++)
		{
			int eres = 0;
			if (!ExprLine(eres)) throw "E4";
			res.emplace_back(eres);
		}
	}

	// Production: EXPRLINE	= EXPR, NEWLINE
	bool ExprLine(int& res)
	{
		if (!Expr(res)) return false;
		if (!NewLine()) throw "E5";
	}

	// Production: EXPR = EXPR OP1 TERM | TERM --> EXPR := TERM {OP1 TERM}
	bool Expr(int& res)
	{
		int t2 = 0;
		char op;
		if (!Term(res)) return false;
		while (Op1(op))
		{
			if (!Term(t2)) throw "E7";
			if (op == '-') res -= t2; // should check for overflow, e.g. using safeint... 
			else res += t2; // may overflow...
		}
		return true;
	}

	// Production: TERM = TERM OP2 FACT | TERM --> TERM = FACT {OP2 FACT}
	bool Term(int& res)
	{
		int f2;
		char op;
		
		if (!Fact(res)) return false;
		while (Op2(op))
		{
			if (!Term(f2)) throw "E9";
			if (op == '*') res *= f2; // may overflow...
			else res /= f2;
		}
		return true;
	}

	// Prodcution:  FACT = INT | '(' EXPR ')' 
	bool Fact(int &res)
	{
		if (Int(res)) return true;
		if (ReadIf('('))
		{
			if (!Expr(res)) throw "E10";
			if (!ReadIf(')')) throw "E11";
			return true;
		}
		return false;
	}

	// Production: OP1 = '+' | '-' 
	bool Op1(char& res)
	{
		res = Peek();
		return ReadIf('+') || ReadIf('-');
	}

	// Production: OP2 = '*' | '/' 
	bool Op2(char& res)
	{
		res = Peek();
		return ReadIf('*') || ReadIf('/');
	}

	// NEWLINE
	bool NewLine()
	{
		return ReadIf('\n');
	}

	// INT
	bool Int(int& res)
	{
		res = 0;
		int sign = 1;
		string digits;

		if (ReadIf('-'))
		{
			sign = -1;
			if (!Digits(digits))
			{
				UnRead(1);
				return false;
			}
		}
		else 
		{
			if (!Digits(digits)) return false;
		}
		
		for (int i = digits.size()-1, f=1; i >=0 ; i--, f*=10)
		{
			res += (digits[i] - '0') * f; // should check overflow with safeint or manually
		}

		res *= sign;
		return true;
	}

	// DIGITS
	bool Digits(string& digits)
	{
		char d;
		digits.clear();
		while (Digit(d))
		{
			digits.append(1, d);
		}
		return digits.size() > 0;
	}

	// DIGIT
	bool Digit(char& c)
	{
		return ReadIfInRange('0', '9', c);
	}

	// Gets the current character (0 at the first call, after Read 1, etc..)
	// returns '\0' if at end
	char Peek() 
	{
		if(_position < _buffer.size()) return _buffer[_position];
		return '\0';
	}

	// Reads the current character if it is =1 (advances the current position)
	bool ReadIf(char a)
	{
		char b;
		return ReadIfInRange(a, a, b);
	}

	// reads the current character if in range [a..b] 
	// e.g. a='0' b='2', reads it if Peek()=='0' or Peek()=='1' or Peek()=='2'
	bool ReadIfInRange(char a, char b, char& c)
	{
		c = Peek();
		if (c >= a && c <= b) 
		{
			Read();
			return true;
		}
		return false;
	}
	
	// Read the current character
	// advances current position unless at end of string
	// note, '\0' may not occure in the string as symbol other then EOF
	char Read()
	{
		char p = Peek();
		if(p != 0) _position++;
		return p;
	}

	// To go back 
	void UnRead(int n)
	{
		_position -= n;
	}
};

int main()
{
	string s1 = "1\n1+2+3*4\n";
	string s2 = "3\n"
		"19+12/4-((4-7)*3/1)\n"
		"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
		"((2+4)/3-2+1)\n";

	cout << "test string s1:" << endl << s1 << endl << endl;
	for (auto i : Parser(s1).Parse()) cout << i << endl;

	cout << endl << endl << "test string s2:" << endl << s2 << endl << endl;
	for (auto i : Parser(s2).Parse()) cout << i << endl;

}

References : geeksforgeeks

package stacks;

import java.util.Stack;

public class Evaluation {


	static Stack<Character> ops = new Stack<Character>();
	static Stack<Integer> numbers = new Stack<Integer>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String expression = "19+12/4-((4-7)*3/1)";
		char[] tokens = expression.toCharArray();
		
		for ( int i = 0 ; i < tokens.length ; i++){
			
			if ( tokens[i] >= '0'  && tokens[i] <='9')	{
				StringBuffer number = new StringBuffer();
				while ( i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')	{
					number.append(tokens[i++]);	
				}
				System.out.println("Number added:" + number);
				i--;
				numbers.push(Integer.decode(number.toString()));
			}
			
			else if (tokens[i] == '(')
				ops.push(tokens[i]);
			
			else if (tokens[i] == ')')	{
				while ( ops.peek() != '(' )	{
					numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
					System.out.println("Number added:" + numbers.peek());
				}
				ops.pop();
			}
			
			else if ( tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/') 	{
				while (!ops.isEmpty() && hasPrecedence( tokens[i] , ops.peek()))	{
					numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
					System.out.println("Number added:" + numbers.peek());
				}
				
				ops.push(tokens[i]);
				System.out.println("Operator added" + ops.peek());
			}
				
		}
		
		while (!ops.isEmpty()){
			numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
		}
		
		System.out.println("Result of expression:" + numbers.pop());
	}

	private static boolean hasPrecedence(char c, Character peek) {
		// TODO Auto-generated method stub
		if ( peek == '(' || peek == ')')
			return false;
		
		else if ( (c == '*' || c== '/' ) && (peek == '+' || peek == '-') )
			return false;
		return true;
	}

	private static int performOp(char pop, Integer num1, Integer num2) {
		// TODO Auto-generated method stub
		if ( pop == '+')	{
			Integer value = num1 + num2;
			return value;
		}
		
		else if ( pop == '-')	{
			Integer value = num2 - num1;
			return value;
		}
		
		else if ( pop == '*')	{
			Integer value = num1 * num2;
			return value;
		}
		
		else {
			System.out.println(num2 + " " + num1);
			Integer value = num2 / num1;
			return value;
		}
		
		
		
	}

}

error: two or more data types in declaration of ‘i’
for (auto int i : Parser(s1).Parse()) cout << i << endl;

^

{"errors":["/usercode/file.cpp: In member function 'void Parser::Program(std::vector<int>&)':\n/usercode/file.cpp:35:17: error: 'class std::vector<int>' has no member named 'emplace_back'\n res.emplace_back(eres);\n ^\n/usercode/file.cpp: In function 'int main()':\n/usercode/file.cpp:212:15: error: 'i' does not name a type\n for (auto i : Parser(s1).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:214:5: error: expected ';' before 'cout'\n cout << endl << endl << \"test string s2:\" << endl << s2 << endl << endl;\n ^\n/usercode/file.cpp:215:5: error: expected primary-expression before 'for'\n for (auto i : Parser(s2).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:215:5: error: expected ')' before 'for'\n/usercode/file.cpp:215:15: error: 'i' does not name a type\n for (auto i : Parser(s2).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n }\n ^\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ')' before '}' token\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n","/usercode/file.cpp: In member function 'void Parser::Program(std::vector<int>&)':\n/usercode/file.cpp:35:17: error: 'class std::vector<int>' has no member named 'emplace_back'\n res.emplace_back(eres);\n ^\n/usercode/file.cpp: In function 'int main()':\n/usercode/file.cpp:212:15: error: 'i' does not name a type\n for (auto i : Parser(s1).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:214:5: error: expected ';' before 'cout'\n cout << endl << endl << \"test string s2:\" << endl << s2 << endl << endl;\n ^\n/usercode/file.cpp:215:5: error: expected primary-expression before 'for'\n for (auto i : Parser(s2).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:215:5: error: expected ')' before 'for'\n/usercode/file.cpp:215:15: error: 'i' does not name a type\n for (auto i : Parser(s2).Parse()) cout << i << endl;\n ^\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n }\n ^\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ')' before '}' token\n/usercode/file.cpp:217:1: error: expected primary-expression before '}' token\n/usercode/file.cpp:217:1: error: expected ';' before '}' token\n"],"all_passed":false,"time":

/* For the fun of it, here Dijkstra's shunting-yard version
   reference: wikipedia / Shunting-yard_algorithm
   
   Simplified for the problem:
   - two stack, one for the numbers that need to be fed into a binary-operation
   - the other for operators/open parentesis (=elements) that haven't been used

   - While there are tokens:
		- Read a token (number, parentesis, operator)
		- if token is number: push on number stack      
			> explanation: 
			> since we read infix notation, we do not know where this number binds to
			> to until we see the next operator or a closing parentesis
		- if token is binary operator (let's say o1):	
			- while o1.precedence <= elementstack.top.precedence: Evaluate() 
			  > we know now, that no operation with a higher precedence was binding to these 
			  > numbers we have seen before, so we can safely evaluate			  
			  > e.g. when the o1.precedence was higher, it was clear that top of number 
			  > stack would be used with the next "number" (or term) and the current o1
			  > (note the = is only valid because we only consider left associative, if 
			  > o1 was right associative it could take the argument away ... ... see wikipedia article
			- push o1 on stack
			  > o1 needs to be evaluated later, of course
		- if open parentesis: push on element stack
		  > explanation this is just a marker, so we know when to stop when the parentesis close
		- if close parentesis: 
			- while(elemenstack.top != closeparentesis: Evaluate()
			  > a closed parentesis tells us that we must evaluate to it's left, regardless 
			  > what follows on the right
			- remove open parentesis from stack
			  > it's been matched with a right parentesis
   - Evaluate until no Bin-Operators are left on elementstack

   Note this version doesn't deal with the unary - eg. -12+24 won't work as well -12+-34 does not work :-)  
*/

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>

using namespace std;

class ExpressionEval
{
private:
	enum class ExprElemType { OpenPar, ClosePar, BinOp };
	struct ExprElem
	{
		char Identifier; // +,-,/, ...
		ExpressionEval::ExprElemType ElementType; 
		int Precedence; // 1,2, ... for Binary Operations
		bool LeftAssocicative; // not used yet
		bool RightAssociative; // not used yet
		int(*BinOperation)(int, int); // the function to do the operation
	};

	istream& _input; // input stream
	stack<const ExprElem*> _elementStack; 
	stack<int> _numStack;

	static const ExprElem ElementTable[6];

public:
	ExpressionEval(istream& input) : _input(input) {}

	int EvaluateExpression()
	{
		// read expression piece by piece
		while (!_input.eof())
		{
			if (_input.peek() == '\n') // get rid of the new line in the input string at the end of expression, in case...
			{
				_input.get();
				break;
			}

			// see if it is an 
			const ExprElem* nextElement = GetExpressionElemenet();
			if (nextElement == nullptr)
			{ // assume it's a number
				int num;
				_input >> num;
				_numStack.push(num);
			} 
			else if (nextElement->ElementType == ExprElemType::BinOp)
			{
				while (!_elementStack.empty() &&
						_elementStack.top()->ElementType == ExprElemType::BinOp && 
						nextElement->Precedence <= _elementStack.top()->Precedence )
					Eval();
				
				_elementStack.push(nextElement);
			}
			else if (nextElement->ElementType == ExprElemType::ClosePar)
			{
				while (!_elementStack.empty() &&
						_elementStack.top()->ElementType != ExprElemType::OpenPar)
					Eval();

				if (_elementStack.empty()) throw "parentesis mismatch";
				_elementStack.pop();
			}
			else if (nextElement->ElementType == ExprElemType::OpenPar)
			{
				_elementStack.push(nextElement);
			}
		}

		// evaluate remainings
		while (!_elementStack.empty()) Eval(); 
		return _numStack.top(); 
	}

private:
	// evaluate expression on the stack (operation on elementstack, numers on numberstack) 
	void Eval()
	{
		if (_elementStack.empty()) throw "operationstack empty";
		if (_numStack.size() < 2) throw "more operators than operands";
		const ExprElem *op = _elementStack.top(); _elementStack.pop();
		if (op->ElementType != ExprElemType::BinOp) throw "support only binary operation at the moment";
		int b = _numStack.top(); _numStack.pop(); 
		int a = _numStack.top(); _numStack.pop();
		_numStack.push(op->BinOperation(a, b));
	}

	// lookup the expression element table and return a pointer to the element or nullptr
	inline const ExprElem* GetExpressionElemenet()
	{
		char op = _input.peek();
		for (auto& elem : ElementTable)
		{ 
			if (elem.Identifier == op) 
			{ 
				_input.get();
				return &elem;
			}  
		}
		return nullptr;
	}
};

// operator table
const ExpressionEval::ExprElem ExpressionEval::ElementTable[6] =
{
	{ '+', ExpressionEval::ExprElemType::BinOp, 1, true, true, [](int a,int b) { return a + b; } },
	{ '-', ExpressionEval::ExprElemType::BinOp, 1, true, false, [](int a,int b) { return a - b; } },
	{ '*', ExpressionEval::ExprElemType::BinOp, 2, true, true, [](int a,int b) { return a * b; } },
	{ '/', ExpressionEval::ExprElemType::BinOp, 2, true, false, [](int a,int b) { return a / b; } },
	{ '(', ExpressionEval::ExprElemType::OpenPar, 0, false, false, nullptr },
	{ ')', ExpressionEval::ExprElemType::ClosePar, 0, false, false, nullptr },
};


int main()
{
	string test = "3\n"
		"19+12/4-((4-7)*3/1)\n"
		"1+(2-3)*4+5-6*8-(18*12*13)-(11/(5+2+4))\n"
		"((2+4)/3-2+1)\n";


	stringstream ss(test);
	int n;
	ss >> n;
	ss.get(); // get that newline
	for (int i = 0; i < n; i++)
		cout << ExpressionEval(ss).EvaluateExpression() << endl;
}