I found an error in my c++ textbook and I can't find a way around it without re-writing the author's stuff completely. An error pops up when I don't use parentheses in the expressions that I enter.
"Expression: string subscript out of range" is the error. Again, this is the author's code. Anyone know whats wrong?
The problem seems to be in this snipit of code:
default : // operand
RPNexp.append(BLANK + token);
for(;;)
{
if ( !isalnum(exp[i+1]) ) break; // end of identifier
i++;
token = exp[i];
RPNexp.append(1, token);
}
Here is the entire thing:
/*-- DStack.h ---------------------------------------------------
This header file defines a Stack data type.
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Accesses the top stack value; leaves stack
unchanged
pop: Modifies stack by removing the value at the
top
display: Displays all the stack elements
Class Invariant:
1. The stack elements (if any) are stored in positions
0, 1, . . ., myTop of myArray.
2. -1 <= myTop < myCapacity
--------------------------------------------------------------*/
#include <iostream>
using namespace std;
#ifndef DSTACK
#define DSTACK
typedef int StackElement;
class Stack
{
public:
/***** Function Members *****/
/***** Constructors *****/
Stack(int numElements = 128);
/*----------------------------------------------------------
Construct a Stack object.
Precondition: None.
Postcondition: An empty Stack object has been constructed
(myTop is initialized to -1 and myArray is an array
with numElements (default 128) elements of type
StackElement).
-----------------------------------------------------------*/
Stack(const Stack & original);
/*----------------------------------------------------------
Copy Constructor
Precondition: original is the stack to be copied and
is received as a const reference parameter.
Postcondition: A copy of original has been constructed.
-----------------------------------------------------------*/
/***** Destructor *****/
~Stack();
/*----------------------------------------------------------
Class destructor
Precondition: None
Postcondition: The dynamic array in the stack has been
deallocated.
-----------------------------------------------------------*/
/***** Assignment *****/
Stack & operator= (const Stack & original);
/*----------------------------------------------------------
Assignment Operator
Precondition: original is the stack to be assigned and
is received as a const reference parameter.
Postcondition: The current stack becomes a copy of
original and a reference to it is returned.
-----------------------------------------------------------*/
bool empty() const;
/*-----------------------------------------------------------
Check if stack is empty.
Precondition: None
Postcondition: Returns true if stack is empty and
false otherwise.
-----------------------------------------------------------*/
void push(const StackElement & value);
/*-----------------------------------------------------------
Add a value to a stack.
Precondition: value is to be added to this stack
Postcondition: value is added at top of stack provided
there is space; otherwise, a stack-full message is
displayed and execution is terminated.
-----------------------------------------------------------*/
void display(ostream & out) const;
/*-----------------------------------------------------------
Display values stored in the stack.
Precondition: ostream out is open.
Postcondition: Stack's contents, from top down, have
been output to out.
-----------------------------------------------------------*/
StackElement top() const;
/*-----------------------------------------------------------
Retrieve value at top of stack (if any).
Precondition: Stack is nonempty
Postcondition: Value at top of stack is returned, unless
the stack is empty; in that case, an error message is
displayed and a "garbage value" is returned.
----------------------------------------------------------*/
void pop();
/*-----------------------------------------------------------
Remove value at top of stack (if any).
Precondition: Stack is nonempty.
Postcondition: Value at top of stack has been removed,
unless the stack is empty; in that case, an error
message is displayed and execution allowed to proceed.
----------------------------------------------------------*/
private:
/***** Data Members *****/
int myCapacity, // capacity of stack
myTop; // top of stack
StackElement * myArray; // dynamic array to store elements
}; // end of class declaration
#endif
/*--------------------------------------------------------------------------
Convert infix expressions to postfix.
Input: An infix expression and user responses
Output: The postfix expression
--------------------------------------------------------------------------*/
#include <iostream> // <<, >>, cout, cin
#include <string> // string, ==, find, npos
#include <cassert> // assert()
#include <cctype> // alnum()
using namespace std;
#include "DStack.h" // Stack class with StackElement = char
string postfix(string exp);
int main()
{
string exp; // infix expression
cout << "NOTE: Enter # for infix expression to stop.\n";
for (;;)
{
cout << "\nInfix expression? ";
getline(cin, exp);
if (exp == "#") break;
cout << "Postfix expression is " << postfix(exp) << endl;
}
}
string postfix(string exp)
/*-------------------------------------------------------------------------
Function to convert an infix expression exp to postfix.
Precondition: exp is received
Postcondition: postfix expression corresponding to exp is returned
or an error message displayed if an error was found in exp.
-------------------------------------------------------------------------*/
{
char token, // character in exp
topToken; // token on top of opStack
Stack opStack; // stack of operators
string RPNexp; // postfix expression
const string BLANK = " ";
for (int i = 0; i < exp.length(); i++)
{
token = exp[i];
switch(token)
{
case ' ' : break; // do nothing -- skip blanks
case '(' : opStack.push(token);
break;
case ')' : for (;;)
{
assert (!opStack.empty());
topToken = opStack.top();
opStack.pop();
if (topToken == '(') break;
RPNexp.append(BLANK + topToken);
}
break;
case '+' : case '-' :
case '*' : case '/': case'%':
for (;;)
{
if (opStack.empty() ||
opStack.top() == '(' ||
(token == '*' || token == '/' || token == '%') &&
(opStack.top() == '+' || opStack.top() == '-'))
{
opStack.push(token);
break;
}
else
{
topToken = opStack.top();
opStack.pop();
RPNexp.append(BLANK + topToken);
}
}
break;
default : // operand
RPNexp.append(BLANK + token);
for(;;)
{
if ( !isalnum(exp[i+1]) ) break; // end of identifier
i++;
token = exp[i];
RPNexp.append(1, token);
}
}
}
// Pop remaining operators on the stack
for (;;)
{
if (opStack.empty()) break;
topToken = opStack.top();
opStack.pop();
if (topToken != '(')
{
RPNexp.append(BLANK + topToken);
}
else
{
cout << " *** Error in infix expression ***\n";
break;
}
}
return RPNexp;
}
/*-- DStack.cpp----------------------------------------------------------
This file implements Stack member functions.
-------------------------------------------------------------------------*/
#include <iostream>
#include <cassert>
#include <new>
using namespace std;
#include "DStack.h"
//--- Definition of Stack constructor
Stack::Stack(int numElements)
{
assert (numElements > 0); // check precondition
myCapacity = numElements; // set stack capacity
// allocate array of this capacity
myArray = new(nothrow) StackElement[myCapacity];
if (myArray != 0) // memory available
myTop = -1;
else
{
cerr << "Inadequate memory to allocate stack \n"
" -- terminating execution\n";
exit(1);
} // or assert(myArray != 0);
}
//--- Definition of Stack copy constructor
Stack::Stack(const Stack & original)
: myCapacity(original.myCapacity), myTop(original.myTop)
{
//--- Get new array for copy
myArray = new(nothrow) StackElement[myCapacity];
// allocate array in copy
if (myArray != 0) // check if memory available
// copy original's array member into this new array
for (int pos = 0; pos < myCapacity; pos++)
myArray[pos] = original.myArray[pos];
else
{
cerr << "*Inadequate memory to allocate stack ***\n";
exit(1);
}
}
//--- Definition of Stack destructor
Stack::~Stack()
{
delete [] myArray;
}
//--- Definition of assignment operator
Stack & Stack::operator=(const Stack & original)
{
if (this != &original) // check that not st = st
{
//-- Allocate a new array if necessary
if (myCapacity != original.myCapacity)
{
delete[] myArray; // destroy previous array
myCapacity = original.myCapacity; // copy myCapacity
myArray = new StackElement[myCapacity];
if (myArray == 0) // check if memory available
{
cerr << "*** Inadequate memory ***\n";
exit(1);
}
}
//--- Copy original's array into this myArray
for (int pos = 0; pos < myCapacity; pos++)
myArray[pos] = original.myArray[pos];
myTop = original.myTop; // copy myTop member
}
return *this;
}
//--- Definition of empty()
bool Stack::empty() const
{
return (myTop == -1);
}
//--- Definition of push()
void Stack::push(const StackElement & value)
{
if (myTop < myCapacity - 1) //Preserve stack invariant
{
++myTop;
myArray[myTop] = value;
}
else
{
cerr << "*** Stack full -- can't add new value ***\n"
"Must increase value of STACK_CAPACITY in Stack.h\n";
exit(1);
}
}
//--- Definition of display()
void Stack::display(ostream & out) const
{
for (int i = myTop; i >= 0; i--)
out << myArray[i] << endl;
}
//--- Definition of top()
StackElement Stack::top() const
{
if ( !empty() )
return (myArray[myTop]);
else
{
cerr << "*** Stack is empty "
" -- returning garbage value ***\n";
return *(new StackElement);
}
}
//--- Definition of pop()
void Stack::pop()
{
if ( !empty() )
myTop--;
else
cerr << "*** Stack is empty -- "
"can't remove a value ***\n";
}