// Project 0: Inheritance in C++, Parsing/ASTs, S-expressions, Polish notation // Write a library for converting between (Polish + S-expr) notation and an AST, and for evaluating these ASTs recursively. // This notation is normal, binary-operator prefix (Polish) notation, but allowing for parentheses to indicate a k-ary use of an operation. Parse these using the normal precedence and associativity, into (strictly) binary operations and literals (natural numbers). // You must support +, -, *, and ^ operators and for each a binary usage where parentheses are optional, and k-ary usage with parentheses required and some caveats below. // These are some examples of equivalent inputs: // + 1 25 => (+ 1 25) // - + 3 2 1 => (- (+ 3 2) 1) // (- 3 2 1) => (- (- 3 2) 1) // (- 2) => (- 0 2) // (+ 3) => 3 // Treat contiguous sequences of digits as a single natural-number token, but all others as single-character symbol tokens. // Parse errors: return null from the parseExp function // e.g., // (* 4) error, * and ^ cannot be used as unary operators // (^ 5) ditto // () error, parens cannot go alone // (+) ditto, operators must have 1 or more operands in all cases // x ditto, only numeric 0-9 characters, whitespace, (, ), +, -, *, ^, are valid input characters // Ignore runtime errors, return any integer // We'll include some STL libraries. We don't need/want any other libraries. #include // needed for std::cin, consider operator>>, and get() functions #include // can be done without strings, but these may be nice #include // for pow() function // Exp is an purely abstract type (or Interface) for Expressions class Exp { public: virtual ~Exp() { } virtual void print() = 0; virtual int eval() = 0; // Must parse an expression from std::cin and return a pointer to an AST, or null to indicate failure static Exp* parseExp(); }; // PlusExp is a concrete type for a (+ ... ...) binary-operation subexpression class PlusExp : public Exp { private: Exp* lhs; Exp* rhs; public: PlusExp(Exp* _lhs, Exp* _rhs) : lhs(_lhs), rhs(_rhs) { } virtual ~PlusExp() { delete lhs; delete rhs; } virtual void print() { // Print as an s-expr std::cout << "("; std::cout << "+ "; lhs->print(); std::cout << " "; rhs->print(); std::cout << ")"; } virtual int eval() { return lhs->eval() + rhs->eval(); } }; // LitExp is a concrete type for a (+ ... ...) binary-operation subexpression class LitExp : public Exp { private: int nat; // A literal is a small natural number, but we'll use int so (-) is closed over this type. public: LitExp(int _n) : nat(_n) { } virtual ~LitExp() { } virtual void print() { std::cout << nat; } virtual int eval() { return nat; } }; // A static function that builds an expression from Polish notation read from STDIN Exp* Exp::parseExp() { std::string token; std::cin >> token; if (token == "+") { Exp* lhs = parseExp(); Exp* rhs = parseExp(); if (lhs && rhs) return new PlusExp(lhs, rhs); if (lhs) delete lhs; if (rhs) delete rhs; return 0; } else try { int n = stoi(token);; return new LitExp(n); } catch (...) { // std::cout << "'" << token << "' not recognized." << std::endl; return 0; // Return null to indicate stoi() failure } }