Quantcast

Maximum PC

It is currently Mon Oct 20, 2014 4:41 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: C++ Recursion issue
PostPosted: Fri Mar 07, 2008 7:51 am 
Monkey Federation (Top 10)*
Monkey Federation (Top 10)*
User avatar

Joined: Sun May 22, 2005 8:28 am
Posts: 3673
Location: The Blue Nowhere
#1 Yes this is homework
#2 I have it working there is one small issue
#3 I just want to be pointed in the right direction or shown where my thinking is off

This problem takes an expression 10 + 10 and evaluates it, the problem is that if I do 10 + (2-1) + anything else it will not evaluate anything after the close paren. I have noted a couple spots where I think the issue could lie but cannot seem to make it work. I think my problem is that the RIGHT_PAREN return is not handled correctly (that is a part of the code that was provided), I have noted them below with comments.

Most of this code was provided so the architecture of the program is not mine and cannot be changed. That is just a limitation of the assignment.


Code:
// Main.cpp
#include "Parse.h"

int main()
{
    Parse parser; 
    string exp;
    bool continueFlag = true;
    while(continueFlag)
    {
        cout << "Enter in an expression (enter quit to exit loop)" << endl;   
        getline(cin, exp);
        if (exp == "quit") continueFlag = false;
        else
        {
            try
            {
                parser.setExpression(exp);
                int value = parser.eval();
                cout << endl << "The value of your expression = " << value << endl;
            }
            catch (Error e)
            {
                cout << "Exception received: "<< endl;
                cout << e.getMsg() << endl;
            }
        }
    }
}

Code:
// Parse.h
#include <iostream>
#include <string>
using namespace std;

enum TokType {NUMBER, VARIABLE, PLUS, MINUS, MULTIPLY, DIVIDE,
              RIGHT_PAREN, LEFT_PAREN, END, WHITE_SPACE, ILLEGAL};

class Token
{
public:
    TokType type;
    int intValue;
};
class VarToken : public Token
{
public:
    string varName;
};

class Error
{
private:
    string m_msg;
public:
    Error(const char * err, const char * src, int loc);
    Error(const char *err);
    const char * getMsg();
};

class Scan
{
private:
    string m_source;
    int m_srcLen;
    int m_currLoc;
    int m_nextLoc;
    VarToken m_currToken;

    bool whiteSpace(char c);
    TokType getType (char c);
   

public:
    Scan();
    void setExpression(string & expressionSource);
    VarToken peekToken();   // return the current token we are on (no scan movement)   
    void  nextToken();   // go to the next token
    VarToken getToken();    // equivalent to peekToken followed by nextToken
    int currLoc();   
};

class EvalVariable
{
public:
    void eval (VarToken & variable);
};

class Parse
{
public:
    Parse ();
    Parse (string &expSource);   
    void setExpression(string & expressionSource);
    int eval();
private:
    string m_source;
    Scan scanner;
    EvalVariable evalVariable;

    int expression();
    // Rules processed by the expression routine
    // expression --> - expression
    // expression --> + expression
    // expression --> term
    // expression --> term + expression
    // expression --> term - expression


    int term();
    // Rules processed by the term routine
    // term -->(expression)
    // term --> value
    // value --> number
    // value --> variable
    // term --> value * term
    // term --> value / term 
};

Code:
// Parse.cpp
#include "Parse.h"

Parse::Parse ()
{
}

Parse::Parse (string &expSource)
{
    setExpression(expSource);
}

void Parse::setExpression(string & expressionSource)
{
    scanner.setExpression(expressionSource);
    m_source = expressionSource;
}

int Parse::eval()
{
    // We might have some other initialization to do if this
    // were inside of a real compiler.

    return expression();
}
   
int Parse::expression()
    // Rules processed by the expression routine
    // expression --> term
    // expression --> term + expression
    // expression --> term - expression
{
    int value = term();

    Token tok = scanner.peekToken();
    if (tok.type == MINUS)
    {
        // Fill in Details
      scanner.nextToken();
      value -= expression();
    }
    else if (tok.type == PLUS)
    {
        // Fill in Details
      scanner.nextToken();
      value += expression();
    }

    return value;   
}


int Parse::term()
    // Rules processed by the term routine
    // term -->(expression)
    // term --> value
    // value --> number
    // value --> variable
    // term --> value * term
    // term --> value / term 
{
    int value ;
    VarToken tok = scanner.peekToken();
    switch (tok.type)
    {         
    case VARIABLE:
        evalVariable.eval(tok);
        // Note that we want to fall into the next case
        // statement (i.e. the number code)
    case NUMBER:
            // Fill in Details
      scanner.nextToken();
      value = tok.intValue;
        break;
    case LEFT_PAREN:
            // Fill in Details
      scanner.nextToken();
      value = term();
        break;

    default:
        throw Error("term contains illegal character ", m_source.c_str(), scanner.currLoc());
    }// end of switch


    tok = scanner.peekToken();
    if (tok.type == MULTIPLY)
        {
            // Fill in Details
         scanner.nextToken();
         value *= term();
        }
    else if (tok.type == DIVIDE)
        {
            // Fill in Details .... Make sure you check for divide
            // by zero.  Throw an exception if you find it.
         scanner.nextToken();
         value /= term();
        }

    return value;
}

Code:
// Scan.cpp
#include "Parse.h"

Error::Error(const char * err, const char * src, int loc)
{
    m_msg = err;
    char cbuff[50];
    sprintf(cbuff," at location: %d in \r\n", loc);
    m_msg += cbuff;
    m_msg += src;
}
Error::Error(const char *err)
{
    m_msg = err;
}
const char * Error::getMsg()
{
    return m_msg.c_str();
}


Scan::Scan()
{
    string init ="";
    setExpression(init);
}
void Scan::setExpression(string & expressionSource)
{
    m_currLoc = 0;
    m_nextLoc = 0;
    m_source = expressionSource;
    m_srcLen = m_source.length();
    nextToken();
}
VarToken Scan::peekToken()   // return the current token we are on (no scan movement)
{
    return m_currToken;
}

void Scan::nextToken() // go to the next token
{
    m_currToken.intValue = -1;
    //skip white space
    while(m_nextLoc < m_srcLen && whiteSpace(m_source[m_nextLoc]))
        m_nextLoc += 1;

    if (m_nextLoc >= m_srcLen)
    {
        m_currToken.type = END;
        return;
    }
///////////////////////////////////////
// The RIGHT_PAREN return goes here but I cannot see where it is handled
    TokType nextType = getType(m_source[m_nextLoc]);
    m_currToken.type = nextType;
    m_currLoc = m_nextLoc++;

    if (nextType == NUMBER)
    {
        while(m_nextLoc < m_srcLen && getType(m_source[m_nextLoc])== NUMBER)
            m_nextLoc += 1;
        // compute value:
        int value = 0;
        for (int i= m_currLoc; i < m_nextLoc; i++)
            value = value *10 + (m_source[i] - '0');
        m_currToken.intValue = value;
    }
    else if (nextType == VARIABLE)
    {
        while (m_nextLoc < m_srcLen)
        {
            TokType t = getType(m_source[m_nextLoc]);
            if (t == NUMBER || t == VARIABLE) m_nextLoc += 1;
            else break;
        }
        m_currToken.varName = m_source.substr(m_currLoc, m_nextLoc - m_currLoc);
    }

}
   
VarToken Scan::getToken()    // equivalent to peekToken followed by nextToken
{
    VarToken retval = m_currToken;
    nextToken();
    return retval;
}
   
int Scan::currLoc()
{
    return m_currLoc;
}


bool Scan::whiteSpace(char c)
    {
        if (c == ' ' || c == '\t' || c=='\r' || c=='\n') return true;
        return false;
    }
   
TokType Scan::getType (char c)
    {
       switch(c)
       {
       case '+':
           return PLUS;
       case '-':
           return MINUS;
       case '*':
           return MULTIPLY;
       case '/':
           return DIVIDE;
       case '(':
           return LEFT_PAREN;
       case ')':
////////////////////////////////////////////////////////////////////////////////
// This return does not have any processing statements
           return RIGHT_PAREN;
       default:
           if (c >= '0' && c <= '9') return NUMBER;
           if (c >= 'a' && c <= 'z') return VARIABLE;
           if (c >= 'A' && c <= 'Z') return VARIABLE;
           if (c == '_' || c == '$') return VARIABLE;           
       }
       if (whiteSpace(c)) return WHITE_SPACE;
       throw Error("Illegal character", m_source.c_str(), m_nextLoc);
    }

Code:
// EvalVariable.cpp
#include "Parse.h"

void EvalVariable::eval (VarToken & variable)
{
    cout << variable.varName <<  " = ?" << endl;
    int value ;
    string exp;
    getline(cin, exp);   
    variable.intValue = atoi(exp.c_str());
}
[/code]


Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 11, 2008 9:33 am 
Coppermine
Coppermine
User avatar

Joined: Mon Feb 21, 2005 9:33 am
Posts: 692
Location: Grass Valley, CA
Well...I don't know how robust your instructor wants this parser. And I don't know how much to tell you, so I'll give it a shot and hopefully not end up doing your homework for you.

This is just a quick patch... If you change the logic of the "expression" function, then that will get you over the first hump of your parser stopping after the closing paren. Now it may be more elegent to handle this elsewhere, but I hope this helps:

Code:
int Parse::expression()
    // Rules processed by the expression routine
    // expression --> term
    // expression --> term + expression
    // expression --> term - expression
{
    int value = term();
   
    Token tok;
    do {
        tok = scanner.peekToken();
        if (tok.type == MINUS)
        {
            // Fill in Details
          scanner.nextToken();
          value -= expression();
        }
        else if (tok.type == PLUS)
        {
            // Fill in Details
          scanner.nextToken();
          value += expression();
        }
        else if (tok.type == RIGHT_PAREN)
        {
          scanner.nextToken();
          break;
        }
    } while (tok.type != END);

    return value;   
}


Top
  Profile  
 
 Post subject:
PostPosted: Thu Mar 13, 2008 5:52 am 
Monkey Federation (Top 10)*
Monkey Federation (Top 10)*
User avatar

Joined: Sun May 22, 2005 8:28 am
Posts: 3673
Location: The Blue Nowhere
Thanks for looking it over. I had already turned it in and failed miserably trying to get the right paren working. Guess I was over thinking the whole issue; I was trying to find a way to end the recursive call and I guess I really didn't need to.


Thanks, at least I know I should not make things harder for myself than they have to be.


Top
  Profile  
 
 Post subject:
PostPosted: Thu Mar 13, 2008 7:41 am 
Coppermine
Coppermine
User avatar

Joined: Mon Feb 21, 2005 9:33 am
Posts: 692
Location: Grass Valley, CA
Ah...bummer. I was hoping to help you get it working before you had to turn it in. :( At least you know what went wrong.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group

© 2014 Future US, Inc. All rights reserved.