Thread: evaluating unary negation operator in an infix expression??

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

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