Reverse Polish Notation - Spreadsheet Calculator

This is for a job I was interviewing for 2 years back.  
Beautiful piece of code I wrote although I never got the job.



Hello John,

It was really nice to talk to you.
Attached is the coding question we send to everyone.  Feel free to use
whatever languages/tools
you are most comfortable with to solve it.  It is not really intended
to be an embedded exercise per se, but rather a way to see how you
might tackle a simple problem.

If you have any questions, feel free to ask. Once we cross this stage
I am looking forward to meet you and YYYY our business development
manager will coordinate with you.

Thanks,
XXXX

Spreadsheet Calculator 
A spreadsheet consists of a two-dimensional array of cells, labeled A1, A2, .... Each cell contains either an integer (its value) or an expression. 

Expressions contain integers, cell references, and the operators '+', '-', '*', '/'. Expressions are given in Reverse Polish Notation (see http://en.wikipedia.org/wiki/Reverse_Polish_notation). Write a program (in Python/C++/Java/C) to read a spreadsheet specification and evaluate the values of all the cells. A spreadsheet is specified as a plain text file:

• Line 1: two integers, defining the width and height of the spreadsheet (n, m) 

• n*m lines each containing an expression which is the value of the corresponding cell (cells enumerated in the order A1, A2, A, B1, ...). 

Your program should output its data in the same format, but each cell should be reduced to a single floating point value.  

Example 
For example, the following spreadsheet: 
2 2
A2
4 5 *
A1 B2 /
3

evaluates to: 
2 2
20
20
6.6666667
3

The above example input visually looks like:

1 2
-------------------------
A | A2 | 4 5 * |
-------------------------
B | A1 B2 / | 3 |
-------------------------

Test Cases
• We provide several example input and output files. • We value elegance, simplicity, and readability in your code 
Comments • All numbers in the input are positive integers, but internal calculations and output should be with floats. You can assume that there are no more than 26 rows (A-Z) in the spreadsheet. • Your program should detect cyclic dependencies in the input data and report these by throwing CircularReferenceException. 
• You may assume that input file is formatted correctly, and all of the expressions are well-formed. 
• Just passing the provided test cases does NOT mean you have a correct implementation.

-------------------

https://github.com/johnsokol/RPN-Spreadsheet-Calculator/

   Attached is a C++ version of the Spreadsheet Calculator.

   input is from Standard in

John

cat test1.in

2 2

A2

4 5 *

A1 B2 /

3

sokol@server:~$ g++ RPNcalc.cpp

sokol@server:~$ ./a.out < test1.in

2 2

20

20

6.66667

3

cat test2.in

3 3

2

3 3 4 + *

A1 B1 +

A2

7

10 C1 /

A1 5 /

B2

3

sokol@server:~$ ./a.out < test2.in

3 3

2

21

23

21

7

25

0.4

7

3

sokol@server:~$ ./a.out < testfail.in

Circular Reference Exception

sokol@server:~$

-------------------

RPNCalc.cpp

-------------------

#include <string>
#include <cctype>
#include <iostream>
#include <map>
#include <sstream>
#include <fstream>
#include <stack>

//  Copyright John L. Sokol - May 21, 2012
//  RPN SpreadSheet Calculator
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//

using namespace std;

#define FALSE 0
#define TRUE 1


namespace Error
{

 struct CircularReferenceException
 {
 };

 struct Zero_divide
 {
 };

 struct Unresolved
 {
 };

 struct Table_error
 {
   const char *p;
     Table_error (const char *q)
   {
     p = q;
   }
 };

 struct Syntax_error
 {
   const char *p;
     Syntax_error (const char *q)
   {
     p = q;
   }
 };
}


class spreadsheet
{

 typedef struct
 {
   std::string data;
   double result;
   bool solved;
 } ElementType;

 typedef map < std::string, ElementType > TableType;

 TableType table;
 int x, y;


public:
 int unresolved_elements;
 bool tablefail;

 enum Token_value
 {
   STRING, NUMBER, PRINT, END, ADD = '+', SUB = '-', MUL = '*', DIV = '/'
 };

   spreadsheet ()
 {
 };

 ~spreadsheet ()
 {
 };

 double RPNeval (string expr);

 void load (istream &);

 void solve_pass ();
 void solve ();

 void dumpresults ();
 void dumpmap ();

};



double
spreadsheet::RPNeval (string expr)
{

 double a, b, result;

#define MATH_OPERATION( op ) \
if(mystack.size() < 2) throw Error::Syntax_error("Stack Underrun"); \
a = mystack.top(); mystack.pop(); \
b = mystack.top(); mystack.pop(); \
mystack.push(b op a);

 stringstream input (stringstream::in | stringstream::out);
 string token;

 stack < double >mystack;
 char ch;

 input << expr;

 while (input.get (ch))
   {
     switch (ch)
{
case 0:
 break; // Should never get here

case '\t':
case ' ':
 break;

case ADD:
 MATH_OPERATION (+)break;
case SUB:
 MATH_OPERATION (-)break;
case MUL:
 MATH_OPERATION (*)break;
case DIV:
 if ((mystack.size () >= 2) && (mystack.top () == 0))
   throw Error::Zero_divide ();
 MATH_OPERATION (/)break;

case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
 input.putback (ch);
 input >> result;
 mystack.push (result);
 break;

default:
 if (isalpha (ch))
   {
     input.putback (ch);
     input >> token;

     if (table.find (token.c_str ()) != table.end ())
{
 if (table[token.c_str ()].solved == 1)
   {
     mystack.push (table[token.c_str ()].result);
   }
 else
   {
     unresolved_elements++;
     throw Error::Unresolved ();
   }
}
     else
throw Error::Syntax_error ("Invalid CELL");

   }
 else
   throw Error::Syntax_error ("Invalid symbol");
}

   }

 result = mystack.top ();
 mystack.pop ();
 return result;
}


void
spreadsheet::load (istream & input)
{
 char tmpstr[255];
 char element[6];
 int i, j;
 stringstream ss (stringstream::in | stringstream::out);

 unresolved_elements = 0;

 cin.getline (tmpstr, 255);
 ss << tmpstr;
 ss >> x;
 ss >> y;
// Check x & y size and throw exception for too large
 if (x > 26 || y > 100)
   {
     throw Error::Table_error ("exceeded maximum size");
     //     exit(1);
   }

 for (i = 0; i < x; i++)
   for (j = 0; j < y; j++)
     {
sprintf (element, "%c%d", 'A' + i, 1 + j);

cin.getline (tmpstr, 255);
table[element].data = tmpstr;
table[element].result = 0;
table[element].solved = FALSE;
unresolved_elements++;
     }
}


void
spreadsheet::solve_pass ()
{
 TableType::const_iterator iter;

 unresolved_elements = 0;
 tablefail = FALSE;

 for (iter = table.begin (); iter != table.end (); iter++)
   {
     try
     {
if (table[iter->first].solved == FALSE)
 {
   table[iter->first].result = RPNeval (iter->second.data);
   table[iter->first].solved = TRUE;
 }
     }
     catch (Error::Unresolved)
     {
// Don't do anything, will try again next passs.
     }
     catch (Error::Syntax_error e)
     {
cerr << "Syntax Error:" << e.p << "\n";
tablefail = TRUE;
     }
     catch (Error::Zero_divide)
     {
cerr << "Divide by Zero Error" << "\n";
tablefail = TRUE;
     }
   }

}


void
spreadsheet::solve ()
{
 int lastunresolved;

 do
   {
     lastunresolved = unresolved_elements;
     //dumpresults();
     solve_pass ();
   }
 while ((unresolved_elements != 0)
&& (unresolved_elements < lastunresolved) && !tablefail);

 if (unresolved_elements != 0 && !tablefail)
   throw Error::CircularReferenceException ();

 if (tablefail)
   throw Error::Syntax_error ("Unable to resolve table");



}

void
spreadsheet::dumpmap ()
{
 TableType::const_iterator iter;

 for (iter = table.begin (); iter != table.end (); iter++)
   {
     cout << iter->first << " = " << iter->second.data << "\n";

   }
}


void
spreadsheet::dumpresults ()
{
 TableType::const_iterator iter;
 cout << x << " " << y << "\n";

 for (iter = table.begin (); iter != table.end (); iter++)
   {
     //cout << iter->first
     if (table[iter->first].solved)
cout << table[iter->first].result ;
     else
cout << "unresolved ";
     cout << "\n";
   }

}


int
main (int argc, char *argv[])
{
 spreadsheet ss;

 try
 {
   ss.load (cin);
   ss.solve ();

   if (ss.unresolved_elements == 0 && !ss.tablefail)
     ss.dumpresults ();

 }
 catch (Error::CircularReferenceException)
 {
   cerr << "Circular Reference Exception\n";
 }
 catch (Error::Syntax_error e)
 {
   cerr << "Syntax Error:" << e.p << "\n";
 }
 catch (Error::Table_error e)
 {
   cerr << "Table Error:" << e.p << "\n";
 }
 return 0;
}