Simple Calculator

#include <StdAfx.h>
#include <fstream>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;


/* - Получаване на ОПЗ ------------------

Докато има символи в израза:
    Прочитаме един символ.
        Ако символът е операнд (число) го добавяме в изходния запис.
        Ако символът е оператор, примерно оп1:
            Докато има оператор, оп2, на върха на стека, и той е с по-голям
            или равен приоритет от оп1:
                Измъкваме оп2 от стека и го поставяме в изходния запис.
            Поставяме оп1 в стека.
        Ако символът е отваряща скоба я поставяме в стека.
        Ако символът е затваряща скоба:
            Докато символът на върха на стека не стане отваряща скоба, измъкваме
                оператори от стека и ги поставяме в изходния запис.
            Премахваме отварящата скоба от стека, без да я поставяме
                в изходния запис.
            Ако стекът се изпразни без да е намерена отваряща скоба в него,
                значи има несъответствие на скобите в израза.
Когато символите от входния израз свършат:
    Докато има символи в стека, измъкваме един:
        Ако символът на върха на стека е скоба (отваряща) значи има несъответствие
            на скобите в израза.
        Измъкваме оператор от стека и го поставяме в изходния запис.
Край.  */


/* --- пресмятане на ОПЗ ---

Докато има символи в ОПЗ
    Прочитаме един символ
    Ако е операнд:
        Поставяме го в стека
    Иначе е оператор:
        Ако на върха на стека има по-малко от 2 операнда
            Грешка: Некоректни входни данни
        Иначе:
            Изваждаме 2 операнда от стека
            Прилагаме оператора върху тях. Първият изваден операнд е
                втори аргумент, а вторият - първи
            Поставяме получената стойност в стека
Ако във стека има само един елемент:
    Това е резултатът
Иначе:
    Грешка: Некоректни входни данни
Край.

*/

struct token
{
    char op;
    int priority;
} tokens[6];


// помощен клас при изработката на ОПЗ

class rpnelem {

    public:

    // едновременно value и op не могат да се укажат, единия от двата се сетва
    // и инстанцията съдържа или стойност или оператор

    float value;
    char op;

    // флаг - дали е число

    bool number;

    // конструктор с оператор

    rpnelem(char newoper) {
        number = false;
        op = newoper;
        value = 0;
    }

    // конструктор по стойност

    rpnelem(float newval) {
        value = newval;
        op = 0;
        number = true;
    }

    bool isoper() {
        if (number)
            return false;
        else
            return (op == ')' || op == '(') ? false : true;
    }

    bool isnumber() {
        return (number);
    }
};

void inittokens()
{
    tokens[0].op='+';
    tokens[0].priority=1;
    tokens[1].op='-';
    tokens[1].priority=1;
    tokens[2].op='*';
    tokens[2].priority=5;
    tokens[3].op='/';
    tokens[3].priority=5;
    tokens[4].op='(';
    tokens[4].priority=10;
    tokens[5].op=')';
    tokens[5].priority=10;
}

// проверява дали символът е оператор
// като скобите не са оператор

bool isoper(char ch)
{
    if(ch != '(' && ch !=')' )
    {
        for(int i=0;i<6;i++)
        {
            if(ch==tokens[i].op)
                return true;
        }
    }
    return false;
}


// проверява дали оператор a е с по-висок приоритет от оператор b

bool isgreater(char a, char b)
{
    char p1,p2;

    for(int i=0;i<6;i++)
    {
     if(a==tokens[i].op)
         p1=tokens[i].priority;
     if(b==tokens[i].op)
         p2=tokens[i].priority;
    }

    return p1>p2;
}

// създава ОПЗ по алгоритъма описан по-горе
// по подаден входящ параметър символен низ

queue <rpnelem>& convert(string& expr)
{
    // помощен стек за създаване на опЗ
    stack <rpnelem> s;

    // резутатът се записва в тази структура опашка
    // като елементи от резултата могат да са както числа
    // така и оператори. ползва се помощен клас rpnelem
    // който позволява запазването с една операция и на двете

    queue <rpnelem> &result = *(new queue <rpnelem>);

    for (int i=0; i < expr.length(); i++)
    {
     //   Ако символът от входния поток
     //   е операнд (число) го добавяме в изходния запис.
     if(expr[i] >= '0' && expr[i] <= '9') {
        result.push(rpnelem((float)(expr[i]-'0')));
        // проверяваме дали няма още цифри числото
        while(i + 1 < expr.length() && expr[i+1] >= '0' && expr[i+1] <= '9' )
             result.back().value = result.back().value * 10 + (expr[++i] - '0');

     }
     //  Ако поредния символ от входния поток
     //  е оператор, (да приемем, че това е ОП1:
     else if(isoper(expr[i]))
     {
         // Докато има оператор (isoper?), ОП2, на върха на стека (s.top()),
         // и той е с по-голям или равен приоритет от ОП1 (isgreater?):
         while(!s.empty() && s.top().isoper() && isgreater(s.top().op, expr[i]))
         {
             //  Измъкваме оп2 от стека и го поставяме в изходния запис.
             //  (заб, тук и result и s работят с елементи от тип <rpnelem>
             //  за това може директно да ги предадем от единия на другия

             result.push(rpnelem(s.top()));

             //  вадим елемента от върха на стека, тъй като той вече е записан
             //  в изходната опашка
             s.pop();
         }

         // Поставяме ОП1 в стека.
         s.push(rpnelem(expr[i]));
     }

     // Ако символът е отваряща скоба я поставяме в стека.
     else if(expr[i]=='(')
         s.push(rpnelem('('));

     // Ако символът е затваряща скоба:
     else if(expr[i]==')')
     {
         // Докато символът на върха на стека не стане отваряща скоба,
         while(s.top().op != '(' && !(s.empty()))
         {
             // измъкваме елементи от стека и ги поставяме в изходния запис.
             // това могат да са както числа, така и оператори

             result.push(s.top());
             s.pop();
         }
         //   Ако стекът се изпразни без да е намерена отваряща скоба,
         // значи има несъответствие на скобите в израза.
         //    заб : в случая ще гръмне с exception
         if (!s.size()) {
             throw logic_error("stack went empty, while no matching bracket was found");

         }

         // Премахваме отварящата скоба от стека, без да я поставяме в изходния
         s.pop();
     }

     // преминаваме към следващия символ
    }

    // Когато символите от входния израз свършат:

    // Докато има символи в стека

    while(!s.empty())
    {
     // ... Измъкваме оператор от стека и го поставяме в изходния запис.
     result.push(s.top());

     //    заб: не е реализирана следната проверка:
     // Ако символът на върха на стека е скоба (отваряща) значи има несъответствие
        //  на скобите в израза.

     s.pop();
    }
    return result;
}

float calculate(queue <rpnelem>& rpnexpr ) {

    stack <rpnelem> s;

    // Докато има символи в ОПЗ

    while (rpnexpr.size()) {
    //    Прочитаме един символ
    //    Ако е операнд:  Поставяме го в стека
        if (rpnexpr.front().isnumber()) {
            s.push(rpnexpr.front());
        } else {
//    Иначе е оператор:
//        Ако на върха на стека има по-малко от 2 операнда
//            Грешка: Некоректни входни данни
            if (s.size() < 2) {
                throw logic_error("operands count does not match");
            }
    //
    //       Иначе:
    //            Изваждаме 2 операнда от стека
    //            Прилагаме оператора върху тях. Първият изваден операнд е
    //            втори аргумент, а вторият - първи
    //                    Поставяме получената стойност в стека

            float arg2 = s.top().value;    s.pop();
            float arg1 = s.top().value;    s.pop();
            switch(rpnexpr.front().op) {
                case '-':
                    s.push(rpnelem(arg2 - arg1));
                    break;

                case '*':
                    s.push(rpnelem(arg2 * arg1));
                    break;

                case '/':
                    s.push(rpnelem(arg2 / arg1));
                    break;

                case '+':
                    s.push(rpnelem(arg2 + arg1));
                    break;

                default:

                    throw logic_error("unknown operator");
            }
        }

        rpnexpr.pop();
    }

    if (s.size() == 1)
        return s.top().value;
    else
        throw logic_error("bad stack count");
    //    Ако във стека има само един елемент:
    //    Това е резултатът
    // Иначе:
    //     Грешка: Некоректни входни данни
    //     Край.
}

int main(int argc, char* argv[])
{
    inittokens();
    string line;
    ifstream file;
    file.open("c:\\temp\\INPUT.TXT");

    if (file.is_open())
     {
         while (!file.eof())
             {
                 getline(file, line);
                 queue <rpnelem> rpnexpr = convert(line);
                 float result = calculate (rpnexpr);
                 cout << line << " = " << result << endl;
             }
         file.close();
     }

    else
        throw logic_error("could not open input file");

    system("PAUSE");
    return 0;
}