evaluating unary negation operator in an infix expression??

Hello,
Thank you for opening the post. I am trying to implement a unary negation operator function to use in my program that uses 2 stacks: a number and operator stack. I get a runtime error in Visual Studio saying "Runtime Check Failure #2: stack around the variable 'nst' was corrupted." If anyone could offer any assistance, I would appreciate it. Thanks a lot in advance.

Below is the full code...

Code:

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

int prec( char op );
long evaluate( char op, long x, long y );
long expon(long x, long y); // function prototype for exponent operator 
long negate(long y); // function prototype for negation operator

int main( )
{
	long nst[41];		// The number stack.
	long ntop = -1;		// The top of the number stack.
	char ost[41];		// The operator stack.
	long otop = -1;		// The top of the operator stack.

	string ebuff;		// Buffers the arithmetic expression.
	int ie;			// Indexes the arithmetic expression.


	// Prompt the user for an expresion and read it.
	cout << "enter arithmetic expression:\n";
	cin >> ebuff;

        // Let's stick a special character at the end of the string.
        ebuff += ']';

	// Put the beginning of line character in the operator stack.
	otop = 0;
	ost[0] = '[';

	// Scan throughout the expression one character at a time.
	for( ie = 0; ; ie++ ) {

		// Stack the numbers immediately.
		if( ebuff[ie] >= '0' && ebuff[ie] <= '9' ) {
			ntop++;
			nst[ntop] = ebuff[ie] - '0';
			continue;
		}
		// We have an operator.  If it is a left parentheses, stack it.
		if( ebuff[ie] == '(' ) {
			otop++;
			ost[otop] = '(';
			continue;
		}
		// Perform as may operations from the stack as the
      // precedence allows.
		while( prec( ost[otop] ) >= prec( ebuff[ie] ) ) {

			// Left paren or [ in stack means we have nothing
         // left to evaluate.
			if( ost[otop] == '[' || ost[otop] == '(' ) break;

			// Perform the indicated operation.
			nst[ntop-1] = evaluate( ost[otop], nst[ntop-1], nst[ntop] );
			ntop--;
			otop--;
		}
		// If we broke out because of matching the beginning of the line,
		// the number on the top of the stack is the result.
		if( ebuff[ie] == ']' ) {
			cout << "value of expression is: " << nst[ntop] << endl;
			return 0;
		}
		// If we broke out due to matching parens, pop the paren
      // out of the stack.
		if( ost[otop] == '(' && ebuff[ie] == ')' ) {
			otop--;
			continue;
		}
		// Stack the operator that we could not evaluate.
		otop++;
		ost[otop] = ebuff[ie];
		continue;
	}
}
// Function to return the precedence value for an operator.
int prec( char op )
{
	switch( op ) {

	case '[':
		return 0;

	case ']':
		return 0;

	case '~':
		return 1;   // negation is done last (PROBLEM AREA)

	case '(':
		return 2;

	case ')':
		return 2;

	case '+':
		return 5;

	case '-':
		return 5;
	
	case '*':
		return 10;

	case '/':
		return 10;

	case '^':
		return 11;  // return 11 since exponent function precedes all others

	default:
		cout << "Illegal operator\n";
		exit( 1 );
		return 0;
	}
}

// Applies an operator to numbers.
long evaluate( char op, long x, long y)
{

	// Based on the operator, perform the operation.
	switch( op ) {

	case '+':
		return x + y;

	case '-':
		return x - y;

	case '*':
		return x * y;

	case '/':
		return x / y;

	case '~':
		return negate(y); // negate quantity at top of stack;

	case '^':
		return expon(x,y);

	default:

		cout << "Illegal operator" << endl;
		exit( 1 );
		return 0;
	}
}

long negate(long y) {

	y = -y; // negate top of stack
	return y; 

}

long expon(long x, long y) {
	int ans=1;

	for (; y!=0; y--) {
		ans = ans*x;
	}

	return ans;
}

Yev

that error means you accessed an array out of bounds somewhere. I only see you accessing nst in two spots, so there are your leads.

Why don't you have a condition for your for loop? I don't see a break to get out of it anywhere either.

Hi,
The loop breaks when the operator stack is [ or ( . The code to break out is in the while loop.

My question is should I be sending a pointer to the number stack in my negate() function?

Any other help is greatly appreciated.


Yev

the while loop breaks when the operator stack has a '[' or '(', not your for loop. So your for loop just keeps on going, and eventually tries to access places it shouldn't be poking its nose into.
Other than that, it seems like your logic should work for the most part.

the while loop breaks when the operator stack has a '[' or '(', not your for loop. So your for loop just keeps on going, and eventually tries to access places it shouldn't be poking its nose into.

The for loop actually ends right here:

Code:

if( ebuff[ie] == ']' ) {
  cout << "value of expression is: " << nst[ntop] << endl;
  return 0;
}

The real problem is this: negation only requires one operand but two are being pulled from the stack because all operators are being evaluated is if they were binary.
(in this code:)

Code:

// Perform the indicated operation.
nst[ntop-1] = evaluate( ost[otop], nst[ntop-1], nst[ntop] );
ntop--;
otop--;

Either categorize the operators into unary/binary groups or just make a special exception for unary negate like this:

Code:

if(ost[otop] == '~')
  nst[ntop] = -nst[ntop];
else
{
  nst[ntop-1] = evaluate( ost[otop], nst[ntop-1], nst[ntop] );
  ntop--;
}
otop--;

This will fix the crashing problem, but due to the awkward precedence for negate, some results may not be as expected.

-tf

Hi,
Thank you for your posts. The code "thefroggy" gave by making the unary negation operator as an exception fails to work and still presents the same runtime problem that stack around the variable nst is corrupted.

Any help is greatly appreciated.

Yev

P.S. You can check yourself by compiling the file below. Just change the extension to .cpp and open in WordPad. (NotePad screws up the formatting)

Please, somebody help me. I am really desperate here!!

Yev

I compiled the code posted below. The only change I made was to correct the precedence for negation. It compiles and runs as expected on DevC++, MSVC 6 and GCC 3.2. You might want to make sure that you've completely rebuilt the entire project after making changes.

Code:

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

int prec( char op );
long evaluate( char op, long x, long y );
long expon(long x, long y); // function prototype for exponent operator 
long negate(long y); // function prototype for negation operator

int main( )
{
	long nst[41];		// The number stack.
	long ntop = -1;		// The top of the number stack.
	char ost[41];		// The operator stack.
	long otop = -1;		// The top of the operator stack.

	string ebuff;		// Buffers the arithmetic expression.
	int ie;			// Indexes the arithmetic expression.


	// Prompt the user for an expresion and read it.
	cout << "enter arithmetic expression:\n";
	cin >> ebuff;

        // Let's stick a special character at the end of the string.
        ebuff += ']';

	// Put the beginning of line character in the operator stack.
	otop = 0;
	ost[0] = '[';

	// Scan throughout the expression one character at a time.
	for( ie = 0; ; ie++ ) {

		// Stack the numbers immediately.
		if( ebuff[ie] >= '0' && ebuff[ie] <= '9' ) {
			ntop++;
			nst[ntop] = ebuff[ie] - '0';
			continue;
		}
		// We have an operator.  If it is a left parentheses, stack it.
		if( ebuff[ie] == '(' ) {
			otop++;
			ost[otop] = '(';
			continue;
		}

		// Perform as may operations from the stack as the
      // precedence allows.
		while( prec( ost[otop] ) >= prec( ebuff[ie] ) ) {

			// Left paren or [ in stack means we have nothing
         // left to evaluate.
			if( ost[otop] == '[' || ost[otop] == '(') break;
			
			// The if statement makes an exception for the only unary negation operator
			if (ost[otop] == '~') {
				nst[ntop] = -nst[ntop];
			}
			// Else, perform the indicated operations on binary groups
			else {
				nst[ntop-1] = evaluate( ost[otop], nst[ntop-1], nst[ntop] );
				ntop--;
			}
			otop--;
			
			
		}
		// If we broke out because of matching the beginning of the line,
		// the number on the top of the stack is the result.
		if( ebuff[ie] == ']' ) {
			cout << "value of expression is: " << nst[ntop] << endl;
      cin.get();
			return 0;
		}
		// If we broke out due to matching parens, pop the paren
      // out of the stack.
		if( ost[otop] == '(' && ebuff[ie] == ')' ) {
			otop--;
			continue;
		}
		// Stack the operator that we could not evaluate.
		otop++;
		ost[otop] = ebuff[ie];
		continue;
	}

}
// Function to return the precedence value for an operator.
int prec( char op )
{
	switch( op ) {

	case '[':
		return 0;

	case ']':
		return 0;

	case '(':
		return 4;

	case ')':
		return 4;

	case '+':
		return 7;

	case '-':
		return 7;
	
	case '*':
		return 10;

	case '/':
		return 10;

  case '~': 
    return 11;

	case '^':
		return 12;  // return 11 since exponent function precedes all others

	default:
		cout << "Illegal operator\n";
		exit( 1 );
		return 0;
	}
}

// Applies an operator to numbers.
long evaluate( char op, long x, long y)
{

	// Based on the operator, perform the operation.
	switch( op ) {

	case '+':
		return x + y;

	case '-':
		return x - y;

	case '*':
		return x * y;

	case '/':
		return x / y;

	case '^':
		return expon(x,y);

	default:

		cout << "Illegal operator" << endl;
		exit( 1 );
		return 0;
	}
}

long expon(long x, long y) {
	int ans=1;

	for (; y!=0; y--) {
		ans = ans*x;
	}

	return ans;
}

-tf