avva | программистская задачка

Коллега недавно предложил следующее задание, которое мне понравилось в качестве разминки:

Написать код, который вычисляет значение числового выражения, использующего скобки и арифметические действия, используя только константное количество локальных переменных. На любом языке. Код должен печатать результат вычисления, или ошибку (можно неинформативную) в случае некорректного ввода.

На входе: строка типа "(2+2)*12" или 56-4*2 или -10^2 итд. Разрешаются скобки и операторы: унарные + и -, бинарные +,-,*,/,^ (возведение в степень). У бинарных операторов обычные уровни приоритета и левая ассоциация внутри уровня, т.е. 10-5-2 равно 3, а не 7. Разрешаются ненужные скобки "(3)". Если в вашем языке нет целочисленной степени, не надо ее имплементировать, можно обойти трюками (напр. в C/C++ перейти к плавающей точке, возвести в степень и округлить). Можно предположить, что все числа и результаты укладываются в размер целочисленного типа вашего языка, если есть такое ограничение. Запрещено использовать массивы, стеки, списки, динамически отведенную память непостоянного размера и другие способы иметь локально неограниченную память в контексте конкретного запуска конкретной функции. Ну и конечно пользоваться чем-то вроде eval() своего языка нельзя, нужно "честно" решить.

Я не утверждаю, что это какое-то особо глубокое или сложное задание, просто хороший способ тряхнуть стариной и элегантно организовать логику. Если вы хотите поучаствовать, присылайте код ссылками на https://pastebin.com/ или свой гитхаб или еще как угодно. Я добавлю ссылку на свое решение (на питоне) завтра вечером к этой записи.

P.S. Поясняю насчет рекурсии. Правила специально сформулированы так ("в контексте конкретного запуска конкретной функции"), что рекурсию МОЖНО использовать. Если вы можете обойтись без рекурсии (я специально не говорю, легко это или тяжело, можно или нельзя), то тоже хорошо, но и рекурсия разрешается.

Update: Спасибо за присланные решения, они все красивые и хорошие :) Мое решение: https://pastebin.com/J6mpMRb2 (исправлены два бага, спасибо комментаторам!).