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;
}
Numerical Explorations 