Parsing String-Converter

Parsing a conversion expression

Page 1 of 1

10 Replies - 2514 Views - Last Post: 25 September 2007 - 04:32 PM Rate Topic: -----

#1 aalloush  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 15-September 07

Parsing String-Converter

Posted 15 September 2007 - 01:13 PM

Hello everone,
I would like to have some help with an assignement:
We would like to create a unit converter that is designed to accept a quantity in one unit
and convert it into another. The program should be flexible enough to convert various
units. For this purpose, we need to use a conversion equation.
The conversion equation is entered in the form of a string containing a list of operands
and operators that will be used to specify how to perform the conversion.
the ex:For example, the general conversion equation used to convert meters to centimeters can
be specified as follows: a*x
After reading the conversion equation, the program needs to perform the following steps:
- traverse the string a*x (this step is known as parsing a string)
- detect that the conversion involves two input operands a and x
- prompt the user to enter the values of these operands (e.g. the user can enter 100
for a and 1 for x)
- detect that the conversion requires to multiply a by x
- perform the multiplication
- output the result (in our case 100)



we didn't take parsing string in class and i would like to know how to begin with that program
and if can anyone give me or explain how parsing works!

thank you

Is This A Good Question/Topic? 0
  • +

Replies To: Parsing String-Converter

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Parsing String-Converter

Posted 16 September 2007 - 08:54 AM

The basics here are not really hard, but this is really a jumping off point where things can get pretty complicated relatively quickly.

To parse a string you need to agree upon a format or more technically a "Grammar" that the message will be in. This is much like saying that in order for a human to parse a sentence they need to know the basics of the grammar for the language the sentence is in.

It looks like your grammar would be something like this:

expression := variable operation variable
variable := {alpha character} (the variable is a single letter)
operation := [+-*/^] (the operation is one of these symbols)

so now you need to create a simple program that recognizes this type of pattern (usually this is done by something called a Finite State Machine, but here you might find it easier just to work it out without all the mathematical/Computer science theory bogging you down).

So read the string on character at a time. First you are looking for a variable (presumable ignoring whitespace), next you are looking for an operation, then you are looking for another variable.

This is really simple to do as long as your grammar is simple as above (even if you allow more variable names such as "temperature" rather than "a") but it does get more complex when you start to allow thing such as:

Expression := (Expression)
Expression := variable name
Expression := Number
Expression := Expression operation Expression
Variable Name := {alpha}{alphanumeric}*
Operation := [+-*/^]

which should be able to handle more general mathematical expression. At this point you really want to get a little more into the theory of Finite state machines and push down automata. At this point you will want to learn about LEX/YACC and compiler theory.
Was This Post Helpful? 0
  • +
  • -

#3 aalloush  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 15-September 07

Re: Parsing String-Converter

Post icon  Posted 16 September 2007 - 10:49 AM

i want to make a program that can resolve the equation.
for example if i write: 5*2+5
the program will give me the result after pressing enter
i have to use a parsing string and its the first time i hear about that
what i understood about a parsing string is that it reads all the character 1 by 1 and do
the work assign for the specific character (in that case it will be only * and +)
I dont know what i have to use as a fonction to be able to do that.
if anyone can give me an example of that i would apreciate his help
thank you
(for exp: how can to make him read the * and amke him resolve it)
Was This Post Helpful? 0
  • +
  • -

#4 PennyBoki  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 55
  • View blog
  • Posts: 2,345
  • Joined: 11-December 06

Re: Parsing String-Converter

Posted 16 September 2007 - 11:16 AM

Hi there, well as per the rules we should see some effort on your side so that someone could help. Also try to search this forum, you could find some similar threads like this one.
Was This Post Helpful? 0
  • +
  • -

#5 aalloush  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 15-September 07

Re: Parsing String-Converter

Posted 16 September 2007 - 11:38 AM

thats what i did till now:
there is some places where i dont know what to put:



#include <iostream>
#include <string>

using namespace::std;
using std::string;

int main(){
	string s;
	


cout<<"Enter the equation you want to use: ";
getline(cin, s);

/*
here the user should write for ex:
	 a*b+c/b
	 
	 how can i make the prog read the equation and ask for 
	 the variables?
*/



if ( int x=s.find("*"))
	  { while(x<string::npos)
	  {
			mult_n(x, y);
			x=s.find("*");
	  }
	  }

else if (int x=s.find("/"))
	  { while(x<string::npos)
	  {
		   div_n(x, y);
		   x=s.find("/");
	  }
	  }
	  
else if (int x=s.find("+"))
	  {while(x<string::npos)
	  {
		   add_n(x, y);
		   x=s.find("+"
	  }
	  }
	  
else if (int x=s.find("-")
	  {while(x<string::npos)
	  {
		  sub_n(x, y);
		  x=s.find("-")
	  }			   
	  }



// CALCULATION:
int mult_n(int x, int y) //multiply 2 numbers
{
	return x*y;	   
}

int div_n(int x, int y) //divide 2 numbers
{
	return x/y;
}

int add_n(int x, int y) //add 2 numbers
{
	return x+y;
}

int sub_n(int x, int y) //subs 2 numbers
{
	return x-y;	
}


}


thank you for ur help
Was This Post Helpful? 0
  • +
  • -

#6 PennyBoki  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 55
  • View blog
  • Posts: 2,345
  • Joined: 11-December 06

Re: Parsing String-Converter

Posted 16 September 2007 - 12:03 PM

First let me say this:
when you post code please use code tags, it's the # button on the posting menu, just select the code and click it.


Now to the code...
I suppose you want your program to work, for a larger equations than this 5*2+5 right? if so then I suggest you use arrays, so that you can store say the ints in one array and the symbols */+- in another array, guess what data type would that be.

Also here is the problem with the priority, you need to consider that to.
And very important thing is that you are going to need variables more than one. Because the only valid variable you've declared is s, well the other are almost valid, but s is the only one declared in the main() scope the others are in it's subscopes. Another thing you should learn is the if statements, because the ones you use a simply wrong.
Was This Post Helpful? 0
  • +
  • -

#7 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Parsing String-Converter

Posted 16 September 2007 - 12:17 PM

Please do not double post your questions. My earlier response should get you going.
Was This Post Helpful? 0
  • +
  • -

#8 PennyBoki  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 55
  • View blog
  • Posts: 2,345
  • Joined: 11-December 06

Re: Parsing String-Converter

Posted 16 September 2007 - 07:32 PM

View PostNickDMax, on 16 Sep, 2007 - 12:17 PM, said:

Please do not double post your questions. My earlier response should get you going.

Actually Nick if you see the code he/she posted, I don't think the member is ready for that, and you are 103% right on with the post.
So I suggest that aalloush learns the basics of C++ first before going any further.
Was This Post Helpful? 0
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Parsing String-Converter

Posted 17 September 2007 - 06:57 AM

If the program only had to deal with "a*b" then I would say that there was no need to learn about Finite State Machines.... but the program has to deal with expressions like: "a*b+c/b". Now you CAN use a non-FSM solution to this, but why?

So we need a basic shell for a finite automata. There are a couple of classic ways to approach this, but normally one choses a variable called a state variable (just and integer that holds a number that tells us what state we are in) and then a great big IF-THEN-ELSE IF-THEN-ELSE-IF-THEN statement (or a switch statement if you prefer). We then move though the string 1 character at a time. Then If-statment looks at the state variable and based upon what state we are in (are we expecting a letter, or an operation, etc) we preform some action and change the state variable for the next character.


here is a bit of pseudocode (i.e I have no C compiler on this computer so I doubt this code would compile -- I never get it right the first time) to get you started:

void parseExpres(char *Exp)
{
	int state = 0; //initial state
	int marker = 0
	int var1 = 0, var2 = 0, operation = 0;
	char ch;


	do {
		//First we want to read in a character... ignoring whitespace
		do {
			ch = Exp[Marker];
			Marker++;
		while (ch == 32); //ignore the space character when we see it.

		if (ch != 0) //ch == 0 is the end of the string...
		{
			if (state == 0) //0 - we are looking for an variable
			{
				if (ch >='a' && ch <='z') //ch is a lower case letter -- works for me
				{
					//ok we found a variable now we need to do something with it...
					//I am not really going to put anything useful here
					cout << "Please enter value for " << ch << ":" << endl;
					cin >> var1;
					
					//we need to change the state!
					state = 1;
				} else {
					//we did not find a variable so the user messed up!!
					cout << "Sorry no valid variable found at: " << marker -1 << endl;
					state = -1;
				}
			} else if (state == 1) //1 - we are looking for an operation
			{
				if (ch == '-')
				{
					operation = 1;
					state = 2;
				} else if (ch == '+')
				{
					operation = 2;
					state = 2
				} //... add the other operations
				else 
				{
					//no valid operation found!!!
					cout << "Sorry no valid operation found at: " << marker - 1 << endl;
					state = -1;
				}
			} else if (state==2) //2 - we are looking for the second variable
			{
				//almost exactly like state 0
				if (ch >='a' && ch <='z') //ch is a lower case letter -- works for me
				{
					//ok we found a variable now we need to do something with it...
					//I am not really going to put anything useful here
					cout << "Please enter value for " << ch << ":" << endl;
					cin >> var2;
					
					//we need to change the state!
					state = 3;
				} else {
					//we did not find a variable so the user messed up!!
					cout << "Sorry no valid variable found at: " << marker -1 << endl;
					state = -1;
				}
			} else if (state==3) //ok we can do an operation!!!
			{
				//by putting the result back into var1 we will allow the user to 
				//enter longer strings...
				if (operation == 1) {var1 -= var2;}
				else if (operation ==2) {var1 += var2;}
				//enter the rest of the operations...
				else
				{
					//no valid operation... some odd error happened
					cout << "Unknown error: The sky is falling!";
					state = -1;
				}
				cout << "The computed value so far is: " << var1 << endl;
				state = 1;
			}
		} else //this means that ch == 0, the end of the string
		{
			if (state == 1) //we were looking for a new operation
			{
				cout << "The final computed value was: " << var1 << endl;
			} else
			{
				cout << "Error while parsing expression!";
			}
		}
	} while (ch!=0 && state != -1);
}


The above (once it is cleaned up and finished) should give you a shell to something that will parse a expression of the sort 'a+b-c*x' it will not parse strings like '(a+B)*c/2'. Read over it a few time. THINK about it. This is the basic idea behind what you want to do... add a stack to this and you would have a push down automata capable of doing complex expressions.
Was This Post Helpful? 0
  • +
  • -

#10 orcasquall  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 158
  • Joined: 14-September 07

Re: Parsing String-Converter

Posted 17 September 2007 - 09:19 AM

I agree that NickDMax's character by character input reading can be combined with stacks to come up with a solution. There's this site detailing a method that I believe can be used to parse a generic expression, and illustrates this idea. It's called reverse polish notation.

Keep the input simple, using a combination of single alphabet, numerals and the four operations (addition, subtraction, multiplication and division), and the code should be easier to write. It might seem a lot of work to restructure an expression into stack form, and then run through the stack to evaluate the expression. It will be a generic parser though. The notation also takes care of parenthesis, so that should be generic enough.

If you really want to, you could even parse trigonometry functions.
Was This Post Helpful? 0
  • +
  • -

#11 borok  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 23-September 07

Re: Parsing String-Converter

Posted 25 September 2007 - 04:32 PM

thats what i did again:
just want to know any other advice and what i should do

 

#include<iostream>
#include<string>

using namespace::std;
using std::string;


void variable_search_1();
void variable_search_2();
void sign_search();  
void operation_to_do();
int total_result();


main()
{   
	string s;
	int state = 0; //initial state
	int site = 0;
	int var1 = 0, var2 = 0, operation = 0;
	char ch;
	int result;

/***************************/
cout<<"Enter the equation: ";

while(getline(cin, s))
{
	   ch=s[site];
	   site++;
	  
	  for(int i=0;i<=s.size();i++)
	  {			 

			if(state==0)
			   {
					variable_search_1();
					//state=1;
			   }
			   else if(state==1)
			   {
					sign_search(ch);	   
					//state=2;
			   }
			   else if(state==2)
			   {
					variable_search_2();
					//state=3;
			   }
			   else if(state==3)
			   {
					operation_to_do(operation);
					//return to state=1 if not finish
			   }
			   else
			   {
					total_result(result);	
			   }
	  }//end for loop
   }//end while loop
}//end main
			   
   
   
   
   
   
   
/*8888888888888888888888888888888888888888888888888888888888888*/
void variable_search_1()//STEP0
{
	 if(ch>='a' && ch<='z')
	 {   
		 if(ch>='A' && ch<='Z')
		 {
			 cout<<"Enter value of "<<ch<<": ";
			 cin>>var_1;
			 state=1;
			   }
		   else 
		   {
			  cout<<"Error: No variable."<<endl;
			  state=-1;
		   }
	 }  
}
/*888888888888888888888888888888888888888888888888888888888888*/
void variable_search_2()//STEP0
{
	 if(ch>='a' && ch<='z')
	 {   
		 if(ch>='A' && ch<='Z')
		 {
			 cout<<"Enter value of "<<ch<<": ";
			 cin>>var_2;
			 state=1;
			   }
		   else 
		   {
			  cout<<"Error: No variable."<<endl;
			  state=-1;
		   }
	 }  
}

/*8888888888888888888888888888888888888888888888888888888888888*/
void sign_search(char ch)//STEP1
{
	 
	 int operation; 
	 
switch(ch)
{	  
	   case'*':
	   operation=1;
	   //state=2;
	   break;
	
	 case'/':
	   operation=2;
	   //state=2;
	   break;			  
	 
	 case'+':
	   operation=3;
	   //state=2;
	   break;		 
	
	 case'-':
	   operation=4;
	   //state=2;
	   break;
	 
	 case'\n': //ignore new line
	 case' ': //ignore entered spaces
	 break;
	 
	 default: 
			  cout<<"Unknown Operation!"<<endl;
			  break;
			  state=-1;
}
			  state=2;

}
/*8888888888888888888888888888888888888888888888888888888888888*/

void operation_to_do(int operation)//STEP2  ---   AFTER STEP 2: STEP 0 AGAIN
{
	 int result=0.0;
	 
switch(operation)
{
	 case'1':
	   var1*=var2;
	   break;
	
	 case'2':
	   var1/=var2;
	   break;			  
	 
	 case'3':
	   var1+=var2;
	   break;		 
	
	 case'4':
	   var1-=var2;
	   break;
	 
	 case'\n': //ignore new line
	 case' ': //ignore entered spaces
	 break;
	 
	 default: 
			  cout<<"Unknown Operation!"<<endl;
			  break;
}   
			  result=var1;
			  cout<<"The result so far is: "<<result<<"."<<endl
			  state=1;
}
			
/*8888888888888888888888888888888888888888888888888888888888888*/ 

int total_result(int result)
{
	  if(state=1)
	  {
	  cout<<"The total result is: "<<result<<"."endl;
	  }
	  else
		  return 0;
}
/*8888888888888888888888888888888888888888888888888888888888888*/






thank you
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1