Category: Number Theory

#pragma once
#include <list>
#include <stack>
#include <string>
#include <vector>
using namespace std;

const char Exp = '^';
const char Mul = '*';
const char Div = '/';
const char Add = '+';
const char Sub = '-';
const char LtParen = '(';
const char RtParen = ')';

class InfixToPostFix
{
public:
	stack<char> numberStack;
	
	int Convert(
		string infixStr, string& postfixStr);
	int EvaluatePostFix(string postfixStr);
	int Priority(char opcode);
};

#include "pch.h"
#include "InfixToPostFix.h"
#include <vector>
using namespace std;

int InfixToPostFix::Convert(
	string infixStr, string& postfixStr)
{
	char ch = 0;
	int number = 0, opcode = 0, opcode1 = 0, parenLevel = 0;
	string numberStr;

	for (size_t i = 0; i < infixStr.size();)
	{
		//while (i < infixStr.size() && infixStr[i] == ' ')
			//i++;

		while (i < infixStr.size() && infixStr[i] >= '0' &&
			infixStr[i] <= '9')
			numberStr.push_back(infixStr[i++]);

		if (numberStr.size() != 0)
		{
			for (size_t j = 0; j < numberStr.size(); j++)
				postfixStr.push_back(numberStr[j]);

			postfixStr.push_back(' ');
			numberStr.clear();
		}

		//while (i < infixStr.size() && infixStr[i] == ' ')
			//i++;

		if (infixStr[i] == '(')
		{
			numberStack.push(infixStr[i]);
			parenLevel++;
		}

		//while (i < infixStr.size() && infixStr[i] == ' ')
			//i++;

		if (infixStr[i] == ')')
		{
			ch = numberStack.top();
			numberStack.pop();

			parenLevel--;

			//while (i < infixStr.size() && infixStr[i] == ' ')
				//i++;

			while (ch != '(')
			{
				postfixStr.push_back(ch);
				postfixStr.push_back(' ');

				parenLevel++;

				ch = numberStack.top();
				numberStack.pop();
			}
		}

		//while (i < infixStr.size() && infixStr[i] == ' ')
			//i++;

		if (infixStr[i] == '^' || infixStr[i] == '*' ||
			infixStr[i] == '/' || infixStr[i] == '+' ||
			infixStr[i] == '-')
		{
			if (numberStack.empty())
				numberStack.push(infixStr[i]);
			else
			{
				ch = numberStack.top();
				numberStack.pop();

				//while (i < infixStr.size() && infixStr[i] == ' ')
					//i++;

				while (Priority(ch) >= Priority(infixStr[i]) &&
					!numberStack.empty() && ch != '(')
				{
					postfixStr.push_back(ch);
					postfixStr.push_back(' ');

					ch = numberStack.top();
					numberStack.pop();
				}

				//while (i < infixStr.size() && infixStr[i] == ' ')
					//i++;

				if (ch != '(')
				{
					if (Priority(infixStr[i]) <= Priority(ch))
					{
						postfixStr.push_back(ch);
						postfixStr.push_back(' ');

						numberStack.push(infixStr[i]);
					}

					else
					{
						numberStack.push(ch);
						numberStack.push(infixStr[i]);
					}
				}
				else
				{
					numberStack.push(ch);
					numberStack.push(infixStr[i]);
				}
			}
		}

		i++;
	}

	while (!numberStack.empty())
	{
		ch = numberStack.top();
		numberStack.pop();

		postfixStr.push_back(ch);
		postfixStr.push_back(' ');
	}

	return 0;
}

int InfixToPostFix::EvaluatePostFix(string postfixStr)
{
	char opcode = 0;
	int charValue = 0, result = 0, value1 = 0, value2 = 0;
	stack<int> intStack;

	for (size_t i = 0; i < postfixStr.size();)
	{
		string numberStr;

		if (postfixStr[i] != ' ')
		{
			while (postfixStr[i] >= '0' && postfixStr[i] <= '9')
				numberStr.push_back(postfixStr[i++]);

			if (!numberStr.empty())
				intStack.push(atoi(numberStr.c_str()));

			else
			{
				value2 = intStack.top();
				intStack.pop();
				value1 = intStack.top();
				intStack.pop();

				opcode = postfixStr[i++];

				if (opcode == '^')
					result = (int)pow(value1, value2);
				else if (opcode == '*')
					result = value1 * value2;
				else if (opcode == '/')
					result = value1 / value2;
				else if (opcode == '+')
					result = value1 + value2;
				else if (opcode == '-')
					result = value1 - value2;

				intStack.push(result);
			}
		}

		else
			i++;
	}

	result = intStack.top();
	intStack.pop();

	return result;
}

int InfixToPostFix::Priority(char opcode)
{
	int result = 0;

	switch (opcode)
	{
	case Exp:
		result = 2;
		break;
	case Mul:
		result = 2;
		break;
	case Div:
		result = 2;
		break;
	case Add:
		result = 1;
		break;
	case Sub:
		result = 1;
		break;
	case LtParen:
		result = 0;
	}

	return result;
}

#include "pch.h"
#include "InfixToPostFix.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    fstream inps, outs;
    char line[256];
    
    inps.open("TestFile.txt", fstream::in);
    outs.open("ResuFile.txt", fstream::out | fstream::ate);

    while (!inps.eof())
    {
        string postfixStr;

        inps.getline(line, 256);

        if (strlen(line) == 0)
            break;

        string infixStr(line, strlen(line));
        InfixToPostFix translate;

        int con = translate.Convert(
            infixStr, postfixStr);

        if (con != 0)
        {
            cout << "Conversion error!" << endl;
            cout << "Error code = " << con << endl;
        }

        else
        {
            char newline[] = { '\n' };

            outs.write(infixStr.c_str(), infixStr.size());
            outs.write(newline, 1);
            outs.write(postfixStr.c_str(), postfixStr.size());
            outs.write(newline, 1);

            int val = translate.EvaluatePostFix(postfixStr);

            if (val < 0)
            {
                cout << "Evaluation error!" << endl;
                cout << "Error code = " << val << endl;
            }

            else
            {
                char buffer[256] = { '\0' };
                string str = "Positive integer value = ";

                _itoa_s(val, buffer, 10);
                
                outs.write(str.c_str(), strlen(str.c_str()));
                outs.write(buffer, strlen(buffer));
                outs.write(newline, 1);
            }
        }
    }

    inps.close();
    outs.close();

    return 0;
}