Create a gist now

Instantly share code, notes, and snippets.

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <limits>
#include <functional>
#include <utility>
#include <stdexcept>
using Number = double;
using NumberSequence = std::vector<Number>;
const Number NaN = std::numeric_limits<Number>::quiet_NaN();
class RecurrenceEvaluator
{
using Instruction = std::function<void(void)>;
using Program = std::vector<Instruction>;
const Instruction _plus, _minus, _times, _divide;
Program _program;
NumberSequence _sequence, _stack;
int _lastIndex;
Number ExecuteProgram();
Number Pop();
template<typename F, bool isDivision=false> Instruction MakeBinaryOp();
Instruction MakeConstant(Number c);
Instruction MakeTap(int k);
public:
RecurrenceEvaluator();
void SetProgram(const std::string &programText);
void SetInitialValue(const std::string &line);
void ComputeValues(int lastIndex);
Number GetValue(int i) const { return _sequence[i]; }
};
static std::string readline()
{
std::string line;
if (!std::getline(std::cin, line))
throw std::runtime_error("input error");
return std::move(line);
}
int main()
{
using namespace std;
RecurrenceEvaluator e;
int n;
try {
string line;
cout << "Enter expression:\n";
line = readline();
e.SetProgram(line);
cout << "Enter initial values; finish with an empty line:\n";
while (line = readline(), !line.empty())
e.SetInitialValue(line);
cout << "Enter count:\n";
if (!(cin >> n) || n < 1)
throw std::runtime_error("invalid count");
e.ComputeValues(n);
} catch (std::runtime_error &err) {
cout << "Error reading input: " << err.what() << endl;
return 1;
}
for (int i = 0; i <= n; ++i) {
Number v = e.GetValue(i);
if (v == v) // NaN?
cout << i << ": " << v << endl;
}
return 0;
}
RecurrenceEvaluator::RecurrenceEvaluator() :
_plus(MakeBinaryOp<std::plus<Number>>()),
_minus(MakeBinaryOp<std::minus<Number>>()),
_times(MakeBinaryOp<std::multiplies<Number>>()),
_divide(MakeBinaryOp<std::divides<Number>, true>()),
_lastIndex(-1)
{
_sequence.reserve(4096);
_stack.reserve(64);
}
void RecurrenceEvaluator::SetProgram(const std::string &programText)
{
std::istringstream iss(programText);
Number num;
char ch;
int tap;
Number sign;
while (iss >> ch)
{
switch (ch)
{
case '(':
if (!(iss >> tap >> ch) || ch != ')')
throw std::runtime_error("error parsing tap");
_program.push_back(MakeTap(tap));
break;
case '+':
_program.push_back(_plus);
break;
case '-':
_program.push_back(_minus);
break;
case '*':
_program.push_back(_times);
break;
case '/':
_program.push_back(_divide);
break;
default:
sign = ch == '~' ? -1 : 1; // Use ~ for negative numbers to avoid ambiguity with subtraction
if (ch != '~')
iss.putback(ch);
if (!(iss >> num))
throw std::runtime_error("error parsing number");
_program.push_back(MakeConstant(sign * num));
break;
}
}
if (_program.empty())
throw std::runtime_error("empty program");
}
void RecurrenceEvaluator::SetInitialValue(const std::string &line)
{
std::istringstream iss(line);
int i;
Number value;
char ch;
if (!(iss >> i >> ch >> value) || ch != ':')
throw std::runtime_error("error parsing initial value");
if (i < 0)
throw std::runtime_error("invalid index for initial value");
if (i >= _sequence.size())
_sequence.resize(i + 1, NaN);
if (i > _lastIndex)
_lastIndex = i;
_sequence[i] = value;
}
void RecurrenceEvaluator::ComputeValues(int lastIndex)
{
if (_lastIndex+1 != _sequence.size())
throw std::logic_error("internal error");
while (++_lastIndex <= lastIndex)
_sequence.push_back(ExecuteProgram());
}
Number RecurrenceEvaluator::ExecuteProgram()
{
for (auto& insn : _program)
insn();
return Pop();
}
Number RecurrenceEvaluator::Pop()
{
if (_stack.empty())
throw std::runtime_error("empty stack");
Number n = _stack.back();
_stack.pop_back();
return n;
}
template<typename F, bool isDivision>
RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeBinaryOp()
{
F f;
return [=]() {
Number y = Pop(), x = Pop();
if (isDivision && y == 0)
_stack.push_back(NaN);
else
_stack.push_back(f(x, y));
};
}
RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeConstant(Number c)
{
return [=]() { _stack.push_back(c); };
}
RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeTap(int k)
{
if (k <= 0)
throw std::runtime_error("invalid tap index");
return [=](){
if (_lastIndex - k < 0)
_stack.push_back(NaN);
else
_stack.push_back(_sequence[_lastIndex - k]);
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment