Как пройти собеседование в игровую индустрию: Калькулятор

[pshenichny]

Очень часто на собеседованиях просят показать, как ты можешь писать код. Прямо здесь и сейчас. Задачи - либо из олимпиадного сборника по информатике, либо калькулятор. При приеме на работу в SkyFallen просили написать калькулятор. Каждая третья игровая контора в Москве тоже предлагает написать калькулятор. За 30-60 минут.

Такую любовь к калькуляторам на собеседовании можно объяснить тем, что все читали "Интервью глазами пострадавшего", а Борис Баткин большой любитель синтаксических/лексических анализаторов.

Самое сложное в калькуляторе - распарсить строку в дерево с приоритетами операций, со всеми скобками и не забыть про одиночный минус.
Высокий приоритет: одинокий минус, скобки, число.
Средний приоритет: умножение, деление.
Низкий приоритет: сложение, вычитание.

Пример парсинга выражения -2*(3+4):



Имея дерево уже легко получить конечный результат.

В дереве можно хранить классы, и считать через виртуальную функцию (для любителей ООП).
В дереве можно хранить данные, и считать через switch (для любителей Pure C).
Так же дерево можно разложить на польскую обратную запись и считать через стек (для любителей Fort).

Самое простое для понимания решение на классах. А если делать через switch - то будет меньше строк кода.

Диаграмма классов:



Собственно, самого кода 131 строка. Парсинг не строгий, следит только за количеством закрывающихся скобок, если что-то не может распарсить, то пишет, что ему не понятно. Ну, и ещё есть проверка деления на ноль.

Код легко расширяемый: ввести функцию (например sin) - добавить один класс и переписать Match, чтобы принимал строчку, а не символ; ввести операцию "a ? b : c" - добавить два класса; и т.д.



#include
#include
#include

// Универсальная операция
class Operation
{
public:
virtual ~Operation() {}
virtual float Eval () const = 0;
};

// Просто число
class Number : public Operation
{
public:
Number (float f) : value (f) {}
virtual float Eval () const { return value; }

private:
float value;
};

// Один операнд
class Unary : public Operation
{
public:
Unary (Operation *op) : one (op) {}
~Unary() { delete one; }

protected:
const Operation *one;
};

// Два операнда
class Binary : public Operation
{
public:
Binary (Operation *l, Operation *r) : left (l), right (r) {}
~Binary() { delete left; delete right; }

protected:
const Operation *left, *right;
};

// Одинокий минус
class Negation : public Unary
{
public:
Negation (Operation *n) : Unary (n) {}
virtual float Eval() const { return - one->Eval(); }
};

// Сложение
class Plus : public Binary
{
public:
Plus (Operation *l, Operation *r) : Binary (l, r) {}
virtual float Eval() const { return left->Eval() + right->Eval(); }
};

// Вычитание
class Minus : public Binary
{
public:
Minus (Operation *l, Operation *r) : Binary (l, r) {}
virtual float Eval() const { return left->Eval() - right->Eval(); }
};

// Умножение
class Multiply : public Binary
{
public:
Multiply (Operation *l, Operation *r) : Binary (l, r) {}
virtual float Eval() const { return left->Eval() * right->Eval(); }
};

// Деление
class Divide : public Binary
{
public:
Divide (Operation *l, Operation *r) : Binary (l, r) {}
virtual float Eval () const
{
const float right_eval = right->Eval ();
return (right_eval != 0.0f) ? (left->Eval() / right_eval) : (printf ("Devide by zero\n"), FLT_MAX);
}
};

class Expression
{
public:
Expression (const char * s) : source (s) {}

float Calc ()
{
pos = 0;
const Operation * const root = Parse0 ();
return (root) ? root->Eval () : 0.0f;
}

private:
// Низкий приоритет: сложение, вычитание
Operation * Parse0 ()
{
Operation * result = Parse1 ();
for (;;)
{
if (Match ('+')) result = new Plus (result, Parse1 ());
else if (Match ('-')) result = new Minus (result, Parse1 ());
else return result;
}
}

// Средний приоритет: умножение, деление
Operation * Parse1 ()
{
Operation * result = Parse2 ();
for (;;)
{
if (Match ('*')) result = new Multiply (result, Parse2 ());
else if (Match ('/')) result = new Divide (result, Parse2 ());
else return result;
}
}

// Высокий приоритет: одинокий минус, скобки, число
Operation * Parse2 ()
{
Operation * result = NULL;
if (Match ('-'))
{
result = new Negation (Parse0 ());
}
else if (Match ('('))
{
result = Parse0 ();
if (! Match (')'))
printf ("Missing ')'\n");
}
else
{
// распарсим число
float val = 0.0f;
if (sscanf_s (source + pos, "%f", & val) == 0)
printf ("Can't parse '%s'\n", source + pos);
result = new Number (val);
while (isdigit (source[pos]) || source[pos] == '.' || source[pos] == 'e') ++pos;
}
return result;
}

// Поищем символ в строке
bool Match (char ch)
{
while (source [pos] == ' ') ++pos; // пропустим пробелы
return (source [pos] == ch) ? (++pos, true) : false; // нашли что искали?
}

private:
const char * source; // исходная строчка
int pos; // текущая позиция
};

int main()
{
char buf [256];
buf [0] = 0;
printf ("Enter expression:\n");
gets_s (buf, 255);

Expression expr (buf);
printf ("Result = %g\n", expr.Calc ());
return 0;
}

Ещё по теме:
Числа
Математика

Порекомендовать: