Solved

writing a parser

Posted on 2000-04-17
3
257 Views
Last Modified: 2010-04-02
will somebody please give me an idea on how to write a parser for algebraic expressions.
  thanks!
0
Comment
Question by:bayz23
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 1

Accepted Solution

by:
ZivKatzir earned 30 total points
ID: 2725469
Hi,
 A very known method for parsing any kind of expressions is using a stack.

The algorithm goes like this :
1. Scan the input stream squentaly.
2. If you find an operand or an operator push it to the stack.
3. When finding a second operand pop the previusly pushed two items. Now if the operator is of high priority (i.e. in your case multiplication or division) calculate it's value and push it back, otherwise push back all 3 items.
4. The result of the first scan will be that in the stack only low priority operations are left. So now scan the stream again using the same loop, but this time it will calculate the final result cause there is no priority diffrences.

In general you have to scan the stream / stack for every different level of priority (precidence).

For validity checks always make sure that you poped from the stack an operator and an operand. If not so the input is wrong.
0
 

Author Comment

by:bayz23
ID: 2742510
i give 20 because, i also need some example of what you are talking about.
0
 
LVL 1

Expert Comment

by:ZivKatzir
ID: 2742982
Hi,
 here is some example written in pseudo
code since I'm a little short at time :

Suppose you want to calculate the value of an arhitmetic expression, given as an input string.
First define a stack to which you can push strings (the stack could be made using an array or a linked list)

Second define a function which cuts the next operator or operand from the string
- GetNextParamFromStr(), assuming the arguments are seperated by spaces and the string ends at NULL.

For example a series of cals to the function over the input string
"5 * 4 - 3" will return :

5
*
4
-
3

Now do as follow :

1. loop : Get a param from the string and save it's type i.e. operator / operand.
2. Match the type of the param with the type you are looking to get (in case of the first param it should be an operand). Inform the user of an error in case of a dismatch.
3. if this is the first param push it to the stack (i.e. using the previous example push '5' to the stack)
4. else if this is an arithmetic operation push it to the stack as well. Using the previous example '*' will be pushed.
5. if this is a number but not the first time pop the previusly pushed operation and number. Now if the poped operation is a high order operation ('*' '/') calculate it's value and push it back to the stack, else push all three parameters back to the stack (i.e. the first number, the operation and the second number).
6. return to step 1 until reaching the end of the string.

Now when the above algorithm is done, your stack will contain only '+' or '-' operations so you can pop the stack parameter at a time and incrementaly calculate the final result.
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
FMX enumerated colours 2 153
Path to  STL Map header file 1 91
Finding Divisors 5 60
calling back function with same name and different signature 1 42
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question