Thread: string parser

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715

    string parser

    I'm trying to make program that will do matrix manipulation: adding, subtracting multiplication etc.
    I would like my program to be similar MATLAB ;user would enter new matrix in
    some similar way:
    example for row vector A=[1,2,3]
    I think that I need to treat this as a string and then go character by charcter to test with isdigit() etc. It would possibly lead to solution but it is rather complicated. Is there another way (conceptualy)?
    And in general case for example program locus32 graph editor you enter (sinx)*exp(-x) and program plots a graph.
    How this is done? I mean (sinx)*exp(-x). Is it by parsing string or how else? I need a few advices on this issue.
    I can solve problem by forcing user to enter number of rows and columns and entering elements through menu, but I'm very interested how this is made in real world.
    Thank you very much!

  2. #2
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    Look at articles about parsers such as recursive descent parsers. Google is always good.
    Do not make direct eye contact with me.

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Yes, I heard and can use google, but then I would be like a blind- man who's looking for something and is not sure what is that exactly. So I post this on this forum hoping someone with a little more experience would give me some advice or a good link. All advices are welcome. Maybe I should post this on C forum but I hope you won't mind
    Thanks

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Here's one way to do it- Take one buffer for the current token and one for unflushed token. As the current token continues to match a certain pattern, it builds until the peek character stops the process by it failing to match that pattern. Then the string is stored away (after the unflushed token is stored). Both buffers are then emptied and the process repeats itself.

    Even better, use regular expressions to define the tokens to the parser, too like:
    ' [a-z, A-Z, _], ['0'-'9', '.'], ["&&"] '
    or:
    ' word=[a-z, A-Z, _], number = ['0'-'9', '.'],
    variable=[[[word]0]word | number], logic_and=["&&"] '

    Once you have all of the tokens assembled there are a number of ways to verify and store the data, interpret as commands - whatever. Just be creative. Helpful functions include strcmp, strstr, find_first_of and find_first_not_of. Good Luck.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Registered User
    Join Date
    May 2003
    Posts
    161
    Here's an example expression parser I posted here a while back. It doesn't include support for variables or functions, but they could be added fairly easily.

    Code:
    #include <locale>
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <vector>
    
    
    using namespace std;
    
    enum TokenType { T_ADD, T_SUBTRACT, T_DIVIDE, T_MULTIPLY, T_NUMBER, T_EOS };
    
    
    struct token
    {
      TokenType type;
      double value;
    };
    
    
    class Scanner
    {
    public:
      void init(istream* is_)
      {
        is = is_;
        next();
      }
    
      token scan()
      {
        token t;
    
        switch(current)
        {
          case T_EOS:
          case ';':
            t.type = T_EOS;
            return t;
          case '+':
            t.type = T_ADD; 
            next();
            return t;
          case '-':
            t.type = T_SUBTRACT;
            next();
            return t;
          case '*':
            t.type = T_MULTIPLY;
            next();
            return t;
          case '/':
            t.type = T_DIVIDE;
            next();
            return t;
          default:
            if(isdigit(current))
            {
              t.type = T_NUMBER;
              t.value = getNumber();
              return t;
            }
            throw string("invalid token");
        }
      }
    
    private:
      istream *is;
      char current;
      ostringstream buffer;
    
      void next()
      {
        if(is->good())
          (*is) >> current;
        else
          current = T_EOS;
      }
    
      double getNumber()
      {
        bool foundDecimal = false;
    
        buffer.str(string());
    
        while((isdigit(current) || current == '.'))
        {
          if(current == '.') 
          {
            if(foundDecimal) 
              throw string("malformed number");
            foundDecimal = true;
          }
    
          buffer << current;
          next();
        }
    
        return atof(buffer.str().c_str());
      }
    };
    
    
    class Parser
    {
    public:
      vector<token> parse(istream* is)
      {
        scanner.init(is);
        tokenSetup = false;
        tokens.clear();
        next();
        expression();
        return tokens;
      }
    
    private:
      Scanner scanner;
      vector<token> tokens;
      token current, lookAhead;
      bool tokenSetup;
    
      void 
      next() 
      { 
        current = lookAhead;
        lookAhead = scanner.scan(); 
    
        if(!tokenSetup)
        {
          tokenSetup = true;
          next();
        }
      }
    
      void 
      expression() { additive_expression(); }
    
      void 
      additive_expression() 
      {
        multiplicative_expression();
    
        while(lookAhead.type == T_ADD || lookAhead.type == T_SUBTRACT)
        {
          token op = lookAhead;
          next(); next();
          multiplicative_expression();
          tokens.push_back(op);
        }              
      }
    
      void multiplicative_expression()
      {
        primary_expression();
    
        while(lookAhead.type == T_MULTIPLY || lookAhead.type == T_DIVIDE)
        {
          token op = lookAhead;
          next(); next();
          primary_expression();
          tokens.push_back(op);
        }      
      }
    
      void primary_expression()
      {
        if(current.type != T_NUMBER)
          throw string("expected number");
    
        tokens.push_back(current);
      }
    
    
    };
    
    
    double Calculate(string expression)
    {
      vector<token>   tokens;
      vector<double>  valueStack;
      Parser          parser;
    
      expression += ";";
    
      istringstream iss(expression);
    
      try 
      { 
        tokens = parser.parse(&iss); 
      }
      catch(string err)
      {
        cerr << "Error: " << err << endl;
        return 0;
      }
    
      vector<token>::iterator itr = tokens.begin();
    
      for( ; itr != tokens.end(); itr++)
      {
        token t = *itr;
    
        if(t.type == T_NUMBER)
          valueStack.push_back(t.value);
        else
        {
          double lhs, rhs, result;
    
          rhs = valueStack.back();
          valueStack.pop_back();
          lhs = valueStack.back();
          valueStack.pop_back();
    
          switch(t.type)
          {
          case T_ADD: result = lhs + rhs; break;
          case T_SUBTRACT: result = lhs - rhs; break;
          case T_MULTIPLY: result = lhs * rhs; break;
          case T_DIVIDE: result = lhs / rhs; break;
          default: break;
          }
    
          valueStack.push_back(result);
        }
    
      }
        
      return valueStack.back();
    }
    
    
    int main()
    {
      string expression, answer;
    
      do
      {
        cout << "Enter an expression: " << flush;
        getline(cin, expression, '\n');
        cout << "Value is: " << Calculate(expression) << endl;
    
        cout << "Enter another? (yes/no) " << flush;
        getline(cin, answer, '\n');
    
      } while(answer[0] == 'y');
    
      return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please check my C++
    By csonx_p in forum C++ Programming
    Replies: 263
    Last Post: 07-24-2008, 09:20 AM
  2. String Class
    By BKurosawa in forum C++ Programming
    Replies: 117
    Last Post: 08-09-2007, 01:02 AM
  3. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 09:19 AM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM