evaluate a given postfix expression containing some one-letter
integer variables a-z (in lower case) whose values are given in a data file.
the name of the data file will be : c:\\temp\\375_prog4_stack_data.txt
and you can hard code this name in your program.
there will not be more than 26 different variables (a-z) and
there will not be more than 20 postfixes for you to process.
the only operators in the post fixes will be : + - * /
all computations are integer computations and all postfixes will be legal.
use a stack of integers and the algorithm below to compute the value of a postfix expression.
algorithm:
scan the given postfix expression left to right char by char:
if char is operand (i.e., a variable a-z)
find its value and push the value on the stack
if the value of the variable is not given, report "invalid variable"
and go to the next problem
if char is an operator + - * /
get the top of the stack (say A) and pop the stack.
again get the top of the stack (say B) and pop the stack.
compute "B operator A" and push the result on stack
if there is any stack problem in the above "report invalid postfix" and
go to the next problem
if there is 0 divide problem report "zero divide" and
go to the next problem
if char is neither variable (anything other than a-z) nor
operator (anything other than + - * /) report "invalid variable"
and go to the next problem
at the end of scanning the postfix,
if stack contains exactly one integer return this value as the answer
if stack has more than one integer report "invalid postfix" and
go to the next problem
end of algorithm
input data format:
the first line gives how many variables there are (n)
the next n lines are the variables and their values separated by a space
the rest of the lines are the POSTFIX expressions that you need to evaluate.
================
5 //this is only a sample; your data may be different
a 4
d 9
z 17
y 0
x 2
aD+
ad+zy-x/*
xz*yd+ad-*+
ab+
ad*yz*+ad**yz*-
adz*+yx/-
zy/
abx^+
code below
=====================================
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstdlib>
#include <istream>
#include <fstream>
#include <stack>
#include <cmath>
#include <math.h>
#include <iomanip>
using namespace std;
// FUNCTION DECLARATIONS
// returns the index of a given character
int get_index(char ch);
// checks to see if a given char is a valid var or not
bool is_alpha(char ch);
// checks to see if a given char is a plus sign
bool is_plus(char ch);
// checks to see if a given char is a minus sign
bool is_minus(char ch);
// checks to see if a given char is a multiplication sign
bool is_mult(char ch);
// checks to see if a given char is a power sign
bool is_power(char ch);
// checks to see if a given char is a division sign
bool is_divide(char ch);
// terminates the program due to invalid postfix
void invalid_postfix_hault( );
void invalid_postfix_hault( string err ); // to give more detail to error message
// GLOBAL VARIABLES
char var[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int value[26] = { 0 }; // initializes to zero.
int _tmain(int argc, _TCHAR* argv[])
{
typedef stack<int> STACK;
int index; // hold the current index
char next; // to use in reading the data file.
int line = 1; // this will keep track of what line in the file we're on.
int numvars; // the number of variables we will need to read in.
// open the 375_prog4_stack_data.txt file for input
ifstream inStream;
inStream.open( "375_prog4_stack_data.txt" );
if ( inStream.fail( ) )
{
cout << "Input file opening failed." << endl;
exit( 1 );
}
// get the number of variables...
inStream.get( next );
numvars = (next - '0');
inStream.get( next ); line++; // skip newline, increment line
// set up the variables...
while (line <= numvars+1)
{
inStream.get( next );
next = tolower(next);
if ( is_alpha( next ) )
{
cout << next;
index = get_index( next );
inStream.get( next ); cout << next; // skip equal sign
inStream.get( next ); cout << next; // first digit
// use a little stack to read in the variable, so it can handle
// numbers > 9
STACK x;
int num = 0; // the value we will eventually end up with
int holder = 0; // temporary holder
int digit = 1; // keeps track of which digits column we are on
while ( next != '\n' )
{
x.push( (next - '0') );
inStream.get( next ); cout << next;
}
while (!x.empty())
{
holder = x.top();
num = num+(holder*digit);
x.pop(); digit = digit*10;
}
value[index] = num;
}
line++;
}
// Now that the numbers are all set up and assigned,
// we'll get to the heart of the program
// This is the main algorithm to evaluate postfix
// expressions.
STACK postfix;
int a = 0; // these will act as temporary holders
int b = 0; //
char test;
while ( !inStream.eof( ) )
{
inStream.get( next );
// if end of line
if ( next == '\n' )
{
// if the stack is empty the postfix must be invalid
if (postfix.empty())
{
inStream.get( next );
if (!inStream.eof())
invalid_postfix_hault( "NO RESULT FOUND" );
inStream.unget();
}
// if the stack has more than one value, the postfix must be invalid
else if (postfix.size() > 1)
{
invalid_postfix_hault( "TOO MANY OPERANDS 1" );
}
else
{
cout << "\t\t= " << postfix.top();
postfix.pop();
}
}
// if it is an operand
else if ( is_alpha( next ) )
{
postfix.push(value[get_index(next)]);
}
// if it is a + operator
else if ( is_plus( next ) )
{
if (postfix.size() > 1)
{
b = postfix.top(); postfix.pop();
a = postfix.top(); postfix.pop();
postfix.push(a+b);
}
else
{ postfix.pop();
invalid_postfix_hault( );
}
}
// if it is a - operator
else if ( is_minus( next ) )
{
if (postfix.size() > 1)
{
b = postfix.top(); postfix.pop();
a = postfix.top(); postfix.pop();
postfix.push(a-b);
}
else
{ postfix.pop();
cout << "\t invalid postfx ERROR " ;
}
}
// if it is a * operator
else if ( is_mult( next ) )
{
if (postfix.size() > 1)
{
b = postfix.top(); postfix.pop();
a = postfix.top(); postfix.pop();
postfix.push(a*b);
}
else
{ postfix.pop();
cout << "\t invalid postfx ERROR " ;
}
}
// if it is a ^ operator
else if ( is_power( next ) )
{
if (postfix.size() > 1)
{
b = postfix.top(); postfix.pop();
a = postfix.top(); postfix.pop();
int temp= (int)pow((double)a,b);
postfix.push(temp);
}
else
{ postfix.pop();
cout << "\t invalid postfx ERROR ";
}
}
// if it is a / operator
else if ( is_divide( next ) )
{
if (postfix.size() > 1)
{
b = postfix.top(); postfix.pop();
a = postfix.top(); postfix.pop();
// watch for divide by zero
if (b != 0)
{
postfix.push(a/b);
}
else
{
cout << "\t DIVIDE BY ZERO";
}
}
else
invalid_postfix_hault( "NOT ENOUGH OPERANDS" );
}
cout << next;
}
// finalize program
return 0;
}
int get_index(char ch)
{
for (int i = 0; i < 26; i++)
{
// check the given character against each variable character
if (var[i] == ch)
return i;
}
return 27;
}
bool is_alpha(char ch)
{
for (int i = 0; i < 26; i++)
{
if ( var[i] == ch )
return true;
}
return false;
}
bool is_plus(char ch)
{
if (ch == '+')
return true;
else
return false;
}
bool is_minus(char ch)
{
if (ch == '-')
return true;
else
return false;
}
bool is_mult(char ch)
{
if (ch == '*')
return true;
else
return false;
}
bool is_power(char ch)
{
if (ch == '^')
return true;
else
return false;
}
bool is_divide(char ch)
{
if (ch == '/')
return true;
else
return false;
}
void invalid_postfix_hault( )
{
// cout << "\t invalid postfx ERROR " << endl;
}
void invalid_postfix_hault( string err )
{
cout << "\t invalid postfx ERROR " << endl;
}http://i132.photobucket.com/albums/q26/Captain_Hooker/ScreenHunter_01Oct132158.gif
seems to work on the first one that is invalid but not on the rest that are not in the file. not sure what to check for now.
