evaluating unary negation operator in an infix expression??

This is a discussion on evaluating unary negation operator in an infix expression?? within the C++ Programming forums, part of the General Programming Boards category; Hello, Thank you for opening the post. I am trying to implement a unary negation operator function to use in ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Question problem with stacks!

    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
    Last edited by YevGenius; 05-09-2004 at 05:43 PM.

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Still seeking help!

    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

  4. #4
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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.

  5. #5
    Registered User
    Join Date
    May 2003
    Posts
    161
    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

  6. #6
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Question The code still gives error!

    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)
    Attached Files Attached Files
    Last edited by YevGenius; 05-10-2004 at 12:39 PM. Reason: attached the program

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    17

    Exclamation Please HELP!!!

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

    Yev
    Last edited by YevGenius; 05-11-2004 at 09:21 AM.

  8. #8
    Registered User
    Join Date
    May 2003
    Posts
    161
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Help with making a Math Expression DLL
    By MindWorX in forum C Programming
    Replies: 19
    Last Post: 07-19-2007, 11:37 PM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 08:15 AM
  5. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21