/** Implementarea formei poloneze cu evaluarea unei expresii numerice, in care:
  *     - fiecare operand este o cifra;
  *     - cei 4 operatori sunt cei aritmetici elementari.
  *
  * Functionalitatea ei se poate extinde pentru orice tipuri de numere si
  * alti operatori.
 */

#include <stdio.h>
#include <ctype.h> // Folosit pentru isdigit

int operatori[100];
int cntOperatori;

int operanzi[100];
int cntOperanzi;

int cuantificator = 0;

int pop_operand()
{
    return operanzi[--cntOperanzi];
}

int pop_operator()
{
    return operatori[--cntOperatori];
}

void push_operanzi(int val)
{
    operanzi[cntOperanzi++] = val;
}

void push_operator(int op)
{
    operatori[cntOperatori++] = op;
}

int peek_operatori()
{
    return operatori[cntOperatori - 1];
}

int compara_operator(int op1, int op2)
{
    /*  Daca diferenta intre operatori este -1 sau 1,
     *  atunci pot fi (+,-), (-,*) sau (*,/).
     */
    /*  Daca suma op1+op2 == 5, atunci combinatia este (-,*),
     *  care este invalida.
     */
    if(abs(op1 - op2) == 1 && (op1 + op2) % 10 != 5)
        return 1;
    if(op2 > op1)
        return 0;

    /*  Este obligatoriu de pus un return final,
     *  desi toate cazurile sunt deja acoperite
     */
    return 1;
}

void calculeazaOperanzi(int operatorUrmator)
{
    /* Compara operatorul urmator cu ultimul opeator din stiva. */
    int ultimOperator = peek_operatori();

    while(cntOperatori > 0 && compara_operator(ultimOperator, operatorUrmator))
    {
        /*  Se extrag operanzii in ordine inversa a stivei,
         *  adica ordinea lor naturala.
         */
        int b = pop_operand();
        int a = pop_operand();
        int op = pop_operator();

        switch(op % 10)
        {
            case 1: push_operanzi(a + b); break;
            case 2: push_operanzi(a - b); break;
            case 3: push_operanzi(a * b); break;
            case 4: push_operanzi(a / b); break;
        }
    }
}

int main()
{
    char exp[] = "1+2*3/4*(5+6-7)-8*9";
    int i, L = strlen(exp);

    for(i = 0; i < L; i++)
    {
        if(isdigit(exp[i])) { // Doar o cifra ca numar
            operanzi[cntOperanzi] = exp[i] - '0';
            cntOperanzi++;
        } else if(exp[i] == '+') {
            calculeazaOperanzi(1 + cuantificator);
            operatori[cntOperatori] = 1 + cuantificator;
            cntOperatori++;
        } else if(exp[i] == '-') {
            calculeazaOperanzi(2 + cuantificator);
            operatori[cntOperatori] = 2 + cuantificator;
            cntOperatori++;
        } else if(exp[i] == '*') {
            calculeazaOperanzi(3 + cuantificator);
            operatori[cntOperatori] = 3 + cuantificator;
            cntOperatori++;
        } else if(exp[i] == '/') {
            calculeazaOperanzi(4 + cuantificator);
            operatori[cntOperatori] = 4 + cuantificator;
            cntOperatori++;
        } else if(exp[i] == '(') {
            cuantificator = cuantificator + 10;
        } else if(exp[i] == ')') {
            cuantificator = cuantificator - 10;
        }
    }
    /*  Fortarea calcularii operanzilor ramasi cu
     *  cel mai neprioritar operator (unul fictiv).
     */
    calculeazaOperanzi(0);

    printf("%s = %d\n", exp, operanzi[0]);

    return 0;
}