Category: C++ Computer Applications

Infix Notation to Postfix Notation and Postfix Evaluator Implemented by James Pate Williams, Jr.

I translated a Pascal program that is found in “Applied Data Structures Using Pascal” by Guy J. Hale and Richard J. Easton. The original Pascal program only used single digits and four arithmetic operators: ‘*’, ‘/’, ‘+’, and ‘-‘. I extended the code to multiple digit positive integers and added an exponentiation operator ‘^’. The priority of the operators is ‘^’, ‘*’, and ‘/’ highest value and ‘+’ and ‘-‘ lowest priority. I could easily add a modulus operator ‘%’ and Boolean bit operators. Extension to negative integers should be a facile operation. Below is the output from my C++ application.

3 + 7 * 8 - 5
3 7 8 * + 5 - 
Positive integer value = 54
3 * 7 - 4 / 2
3 7 * 4 2 / - 
Positive integer value = 19
(3 + 7) * 8 - 5
3 7 + 8 * 5 - 
Positive integer value = 75
(3 + 4) * 8 - (7 * 3 - 4)
3 4 + 8 * 7 3 * 4 - - 
Positive integer value = 39
(100 + 50) * 20 - 100 / 2
100 50 + 20 * 100 2 / - 
Positive integer value = 2950
2 ^ 16 - 5 * 100
2 16 ^ 5 100 * - 
Positive integer value = 65036


#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;
}

Arithmetic Expression Evaluator in C++ Implemented by James Pate Williams, Jr.

I translated to C++ and enhanced a Pascal arithmetic expression evaluator program found in “Applied Data Structures Using Pascal” by Guy J. Hale and Richard E. Easton. The original code used single digit numbers. As an exercise I enhanced the application to utilize multiple digit numbers. Below is my test file and output from my program. I used the C++ standard library stack data structure.

20 + 3 * 4 + 50 * 4 * 2 + 6 * 2 - 8 / 2 + 2 ^ 5
#pragma once
#include <fstream>
#include <stack>
using namespace std;

class Expression
{
public:
	char ch, sign, termOp;
	int number;

	stack<int> stk;

	void GetChar(fstream& inps);
	void GetExpression(fstream& inps);
	void GetFactor(fstream& inps);
	void GetTerm(fstream& inps);
};

#include "pch.h"
#include "Expression.h"
#include <math.h>
#include <fstream>
#include <stack>
#include <string>
using namespace std;

void Expression::GetChar(
	fstream& inps)
{
	while (!inps.eof())
	{
		ch = (char)inps.get();

		if (inps.eof())
			exit(1);

		if (ch >= '0' && ch <= '9')
			return;

		if (ch == '^' || ch == '*' || ch == '/')
			return;

		if (ch == '+' || ch == '-')
			return;

		if (ch == ' ' || ch == '\t' || ch == '\n')
			continue;

		if (ch == ';')
			return;
	}
}

void Expression::GetExpression(fstream& inps)
{
	int num, num1, num2;

	if (ch == '+' || ch == '-')
	{
		sign = ch;

		GetChar(inps);		
		GetTerm(inps);

		if (sign == '-')
		{
			num = stk.top();
			stk.pop();
			num = -num;
			stk.push(num);
		}
	}

	GetTerm(inps);
	
	while (ch == '+' || ch == '-')
	{
		termOp = ch;
		
		GetChar(inps);
		GetTerm(inps);
		
		num2 = stk.top();
		stk.pop();
		num1 = stk.top();
		stk.pop();

		if (termOp == '+')
			num = num1 + num2;
		else
			num = num1 - num2;

		stk.push(num);
	}
}

void Expression::GetFactor(fstream& inps)
{
	if (ch >= '0' && ch <= '9')
	{
		string str;

		while (ch >= '0' && ch <= '9' && !inps.eof())
		{
			str += ch;
			ch = (char)inps.get();

			if (ch == ' ' || ch == '\t' || ch == '\n')
				break;

			else if (ch == '^' || ch == '+' || ch == '-' ||
				ch == '*' || ch == '/')
				break;
		}

		if (inps.eof())
			exit(-1);

		while (ch == ' ' || ch == '\t' || ch == '\n')
			ch = (char)inps.get();

		number = atoi(str.c_str());
		stk.push(number);
		return;
	}
	else
	{
		GetChar(inps);
		GetExpression(inps);
		GetChar(inps);
	}
}

void Expression::GetTerm(fstream& inps)
{
	char factOp;
	int num, num1, num2;

	GetFactor(inps);

	while (ch == '*' || ch == '/' || ch == '^')
	{
		factOp = ch;

		GetChar(inps);
		GetFactor(inps);

		num2 = stk.top();
		stk.pop();
		num1 = stk.top();
		stk.pop();

		if (factOp == '*')
			num = num1 * num2;
		else if (factOp == '/')
			num = num1 / num2;
		else if (factOp == '^')
			num = (int)pow(num1, num2);

		stk.push(num);
	}
}

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

int main()
{
    bool validExp;
    int expVal;
    fstream inps;
    Expression ex;

    inps.open("TestExp.txt", fstream::in);
    
    if (!inps.eof())
    {
        validExp = true;
        ex.GetChar(inps);
        ex.GetExpression(inps);
        expVal = ex.stk.top();
        ex.stk.pop();
        cout << "Value = " << expVal << endl;
    }

    else
    {
        validExp = false;
        expVal = 0;
    }

    return 0;
}

An Assignment Statement Syntactic Scanner for a Language resembling ADA or Pascal Implemented by James Pate Williams, Jr.

I am working my way through two compiler textbooks: “Design of Compilers Techniques of Programming Language Translation” by Karen A. Lemone and “Modern Compiler Implementation in Java” by Andrew W. Appel. My first exercise is a single line by line assignment statement parser.

Here is my source code and my translation structures:

X1:=a+bb*12;
X2:=a/2+bb*12;

Identifiers:
X1
a
bb
Literals:
12
Operators:
:=
+
*
Punctuation:
;

Identifiers:
X2
a
bb
Literals:
2
12
Operators:
:=
/
+
*
Punctuation:
;

#pragma once
#include "RegularExpAssignStm.h"
#include <string>
#include <vector>
using namespace std;

class RegularExpAssignStm
{
public:
	string punctuation[3] = { ";", "(", ")" };
	string upperCase =
		"ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string lowerCase =
		"abcdefghijklmnopqrstuvwxyz";
	string dig = "0123456789";
	string ops[5] = { "+", "-", "*", "/", ":="};
	vector<string> identifier;
	vector<string> liter;
	vector<string> oper;
	vector<string> punc;

	RegularExpAssignStm() {	};
	bool IdContains(char key);
	size_t Search(size_t pos, string key, string match);
	size_t SingleCharSearch(char key, size_t index, string match[]);
	bool GetIdentifier(string assignStm);
	bool GetLiteral(string assignStm);
	bool Parse(string assignStm);
};



#include "pch.h"
#include "RegularExpAssignStm.h"
#include <functional>
#include <iostream>
#include <string>
using namespace std;

bool RegularExpAssignStm::IdContains(char key)
{
	bool dg = false, uc = false, lc = false;

	for (size_t i = 0; !uc && i < upperCase.size(); i++)
		uc = key == upperCase[i];

	if (uc)
		return true;

	for (size_t i = 0; !lc && i < lowerCase.size(); i++)
		lc = key == lowerCase[i];

	if (lc)
		return true;

	for (size_t i = 0; !dg && i < dig.size(); i++)
		dg = key == dig[i];

	if (dg)
		return true;

	return false;
}

size_t RegularExpAssignStm::Search(size_t pos, string key, string match)
{
	bool found = false;
	size_t i;

	for (i = 0; !found && i < match.size(); i++)
		found = key[pos] == match[i];

	if (!found)
		i = 4294967295;
	else
		i--;

	return i;
}

size_t RegularExpAssignStm::SingleCharSearch(
	char key, size_t index, string match[])
{
	bool found = false;
	size_t i;

	for (i = 0; !found && i < match[index].size(); i++)
		found = key == match[index].c_str()[i];

	if (!found)
		i = 4294967295;
	else
		i--;

	return i;
}

bool RegularExpAssignStm::GetIdentifier(string assignStm)
{
	string idStr;

	for (size_t i = 0; i < dig.size(); i++)
		if (assignStm[0] == dig[i])
			return false;

	for (size_t i = 0; i < assignStm.size(); i++)
	{
		if (IdContains(assignStm[i]))
			idStr.push_back(assignStm[i]);
		else
			break;
	}

	if (idStr.size() > 0)
		identifier.push_back(idStr);

	return idStr.size() > 0;
}

bool RegularExpAssignStm::GetLiteral(string assignStm)
{
	bool start = false;
	string litStr;

	for (size_t i = 0; !start && i < assignStm.size(); i++)
	{
		if (assignStm[0] == dig[i])
			start = true;
	}
	
	if (start)
	{
		liter.push_back("");

		for (size_t i = 0; i < assignStm.size(); i++)
		{
			if (assignStm[i] >= '0' && assignStm[i] <= '9')
				liter[liter.size() - 1].push_back(assignStm[i]);
			else
				return liter.size() > 0;
		}
	}

	return false;
}

bool RegularExpAssignStm::Parse(string assignStm)
{
	if (GetIdentifier(assignStm))
		assignStm.erase(0, identifier[identifier.size() - 1].size());
	else
		return false;

	size_t assignOpPos = Search(0, assignStm, ops[4]);

	if (assignOpPos != 4294967295)
	{
		assignStm.erase(0, ops[4].size());
		oper.push_back(ops[4]);
	}

	else
		return false;

	while (true)
	{
		if (GetLiteral(assignStm))
		{
			assignStm.erase(0, liter[liter.size() - 1].size());

			if (assignStm.size() <= 0)
				return false;
		}

		else if (GetIdentifier(assignStm) &&
			identifier[identifier.size() - 1].size() != 0)
		{
			assignStm.erase(0, identifier[identifier.size() - 1].size());
			
			if (assignStm.size() <= 0)
				return false;
		}

		size_t plusPos, minusPos, timesPos, divPos;

		plusPos = SingleCharSearch(assignStm[0], 0, ops);
		minusPos = SingleCharSearch(assignStm[0], 1, ops);
		timesPos = SingleCharSearch(assignStm[0], 2, ops);
		divPos = SingleCharSearch(assignStm[0], 3, ops);

		if (plusPos != 4294967295)
		{
			oper.push_back(ops[0]);
			assignStm.erase(0, 1);
		}
		else if (minusPos != 4294967295)
		{
			oper.push_back(ops[1]);
			assignStm.erase(0, 1);
		}
		else if (timesPos != 4294967295)
		{
			oper.push_back(ops[2]);
			assignStm.erase(0, 1);
		}
		else if (divPos != 4294967295)
		{
			oper.push_back(ops[3]);
			assignStm.erase(0, 1);
		}
		else
			return false;

		if (assignStm.size() <= 0)
			return false;

		if (GetLiteral(assignStm))
		{
			assignStm.erase(0, liter[liter.size() - 1].size());
			
			if (assignStm.size() <= 0)
				return false;
		}

		else if (GetIdentifier(assignStm) &&
			identifier[identifier.size() - 1].size() != 0)
		{
			assignStm.erase(0, identifier[identifier.size() - 1].size());
			
			if (assignStm.size() <= 0)
				return false;
		}

		size_t puns = SingleCharSearch(assignStm[0], 0, punctuation);

		if (puns != 4294967295)
		{
			punc.push_back(punctuation[puns]);
			assignStm.erase(0, punc[punc.size() - 1].size());

			if (assignStm.size() <= 0)
				return false;
		}
	}

	return true;
}

Create an Index Using C++ and the Map Data Structure Designed and Implemented by James Pate Williams, Jr.

I recall that way back in the early to mid-1980s I had the pleasure of perusing a copy of the source code for a Pascal compiler. It was probably created directly under the inventor Nicklaus Wirth in Switzerland. I partially implemented a Pascal emulator for a Data General Eclipse minicomputer.

Here are some of the phases required for the creation of a Pascal computer program:

  1. Parse the source code.
  2. Create a symbol table.
  3. Interpret the symbols.
  4. Create P-Code for the interpreter.

Running the interpreter code involves translation of the P-Code to a computer readable bit string. Every computer scientist should at some time in her/his formal education should implement an assembler and a compiler.

Yesterday, April 11, 2023, I created a word index C++ application that takes a text file, parses the words, and creates an index also known as an English language symbol table. The app utilizes a C++ map that consists of integer keys and a node containing information about the words and their order in the text file. Below are the indexable text file and the symbol table (index).

This is a test of my index generator. The text file has

two lines. The second line is dummy definitions.

This is a test of my index generator. The text file has
two lines. The second line is dummy definitions.
The first number is the line number and the second the position within a line.

The         1             39          
The         2             12          
This        1             1            
a              1             9            
definitions           2             37          
dummy 2             31          
file          1             48          
generator            1             28          
has         1             53          
index     1             22          
is             2             28          
is             1             6            
line         2             23          
lines       2             5            
my          1             19          
of            1             16          
second  2             16          
test        1             11          
text        1             43          
two        2             1