#include <iostream>
#include <cstring>

using namespace std;


#define MAX_LEN 256
typedef struct
{
    char mas[10];
}stack; //

void push(stack *_stack, int &_ptr, char data[]);
void pop(stack *_stack, int &_ptr, char *data, int enter);
int pow_int(int a,int b);
void push_int(int *_stack, int &_ptr, int data);
int pop_int(int *_stack, int &_ptr);


//  Преобразование записи математ. выражения из инфиксной в постфиксную (в обратную польскую запись) и вычисление данного выражения
//
//  Сразу оговоримся, допустимые операторы: +,-,*,/,(,),^; все операции будем считать лево-ассоциативными
//  Все операнды - односимвольные
//
void PostfixNotation(const char *_infix, char *_postfix)
{
    stack stack[100];
    int st_ptr = 0;             // указатель вершины стека
    int out_index = 0;      // индекс в выходной строке
    int in_index = 0;       // индекс во входной строке
    for(int i = 0; i < 100; i++)
    {
        for(int j = 0; j < 10; j++)
            stack[i].mas[i] = 0;
    }
    // начинаем разбор входящей строки (она не должна быть пустой)
    do
    {
        char c[1];  // берем текущий символ входной строки
        c[0] = _infix[in_index];
        int j = 0;
        switch (c[0])
        {
            case '+':
            case '-':
                // выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
                while (st_ptr != 0)
                {
                    char op = stack[st_ptr-1].mas[0];   // оператор в вершине стека
                    if (op != '(')  // все операторы, кроме откр. скобки имеют больший или равный приоритет
                    {
                        _postfix[out_index++] = op; // добавляем оператор в выходную строку
                        pop(stack, st_ptr, 0, 0);           // удаляем оператор из стека
                    }
                    else
                        break;
                }
                // помещаем оператор в стек
                push(stack, st_ptr, c);
                break;

            case '*':
            case '/':
                // выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
                while (st_ptr != 0)
                {
                    char op = stack[st_ptr-1].mas[0];
                    if ((op == '^') || (op == '*') || (op == '/'))
                    {
                        _postfix[out_index++] = op; // добавляем оператор в выходную строку
                        pop(stack, st_ptr, 0, 0);           // удаляем оператор из стека
                    }
                    else
                        break;
                }
                // помещаем оператор в стек
                push(stack, st_ptr, c);
                break;

            case '(':
                // просто помещаем в стек
                push(stack, st_ptr, c);
                break;

            case ')':
                // выталкиваем из стека в выходную строку все элементы до открывающей скобки (откр. скобку просто отбрасываем)
                while (st_ptr != 0)
                {
                    char* op;
                    pop(stack, st_ptr,op,0);    // забираем из стека оператор
                    if (op[0] == '(')                   // если достигли открывающей скобки
                        break;                      // выталкивание закончили
                    else
                    {
                        _postfix[out_index++] = op[0];  // добавили оператор в выходную строку
                    }
                }
                break;

            case '^':
                // помещаем оператор в стек (выталкивать ничего не нужно, нет операторов с большим приоритетом)
                push(stack, st_ptr, c);
                break;

            default:        // символ цифры
                _postfix[out_index] = c[0]; // добавляем цифру в выходную строку
                out_index++;
                break;
        }

        in_index++; // переходим к следующему символу входной строки
    }
    while (_infix[in_index] != 0);  // разбор закончен

    // выталкиваем все операторы в выходную строку
    while(st_ptr != 0)
        pop(stack, st_ptr, _postfix, out_index);


    // завершающий символ нуля
    //_postfix[out_index] = 0;
}

int calculation(const char* postfix, int x)
{
    int stack[MAX_LEN]; // стек для хранения операндов
    int st_ptr = 0;     // указатель вершины стека

    int temp,temp1; // Временная переменна
    int in_index = 0; // Счетчик массива постфиксной записи

    int op_a, op_b; // Переменные для вычисления выражения

    do
    {
        char c = postfix[in_index];
        if (((c >= '0') && (c <= '9')) || c == 'x') // Если число
        {
            if(c == 'x')
                temp = x;
            else
                temp = c - '0';
        }
        else
        {
            op_b = pop_int(stack, st_ptr); // Выталкиваем два оператора из стека
            op_a = pop_int(stack, st_ptr);

            switch(c) // Производим операции в зависимости от операнда и записываем их во временную переменную
            {
                case '+':
                    temp = op_a + op_b;
                    break;
                case '-':
                    temp = op_a - op_b;
                    break;
                case '*':
                    temp = op_a * op_b;
                    break;
                case '/':
                    temp = op_a / op_b;
                    break;
                case '^':
                    temp = pow_int(op_a, op_b);
                    break;
                default:
                    cout << "Unknown operation " << c << endl;
                    exit(EXIT_FAILURE);
            }
        }
        push_int(stack, st_ptr, temp); // Кладем на вершину стека временную переменную, переходим к следующему символу постфиксной записи
        in_index++;
    }
    while(postfix[in_index] != 0);

    return pop_int(stack, st_ptr); // К концу алгоритма на вершине стека будет записан результат вычисления данного выражения
}



void push(stack *_stack, int &_ptr, char data[])
{
    for(int i = 0; i <= strlen(data); i++)
        _stack[_ptr].mas[i] = data[i];
    _ptr++;
}

void pop(stack *_stack, int &_ptr, char *data, int enter)
{
    --_ptr;
    for(int i = 0; i <= strlen(_stack[_ptr].mas); i++)
    {
        data[enter++] = _stack[_ptr].mas[i];
        cout << _stack[_ptr].mas[i];
    }
}

void push_int(int *_stack, int &_ptr, int data)
{
    _stack[_ptr++] = data;
}

int pop_int(int *_stack, int &_ptr)
{
    return _stack[--_ptr];
}

int pow_int(int a, int b)
{
    int res = a;
    while (b >= 2)
    {
        res = res * a;
        b--;
    }
    return res;
}


int main()
{
    char str_infix[] = "3,4+2,8*x";
    char str_postfix[MAX_LEN];
    int result;
    PostfixNotation(str_infix,str_postfix);
    cout << str_postfix;
    result = calculation(str_postfix,42);
    cout << result << endl;
    return 0;
}