interesting problem

Discussion in 'C Programming' started by makko, Jan 21, 2005.

  1. makko

    makko Guest

    Hello,
    anyone know how to writre a program that take a commandline formula
    and prints the calculated result? example;
    $program 1+(2x3(3/2))-8

    reagrds;
    Makkko
     
    makko, Jan 21, 2005
    #1
    1. Advertising

  2. makko

    Lew Pitcher Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    makko wrote:
    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8


    Yes, I know how.

    For a clue as to how you can know how too, google for "recursive descent
    parser"

    - --

    Lew Pitcher, IT Consultant, Enterprise Data Systems
    Enterprise Technology Solutions, TD Bank Financial Group

    (Opinions expressed here are my own, not my employer's)
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.4 (MingW32)

    iD8DBQFB8QqvagVFX4UWr64RAnfhAKDSEGoKDT0pBPrGbmK/+pfq91RmwACfSDHl
    bBxjlAt+dxVAdzVE3EgHIww=
    =jM5G
    -----END PGP SIGNATURE-----
     
    Lew Pitcher, Jan 21, 2005
    #2
    1. Advertising

  3. makko wrote:

    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8
    >
    > reagrds;
    > Makkko
    >

    #!/usr/bin/perl -w
    print eval("@ARGV") . "\n";

    That'll do it :)

    Your question feels lame to me. The answer is that yes,
    most regulars here know how to write such a program. Do
    you? Have you tried? If you present your efforts here,
    working or not, people are usually quite helpful. Or even
    if you ask nicely for hints on how to get started. But
    asking folks to write your homework for you -- whether for school
    or you are trying to learn to program on your own --
    is feeble.

    If you just want the answers and to learn nothing, google
    will give you source code for this...

    -David
     
    David REsnick, Jan 21, 2005
    #3
  4. On Fri, 21 Jan 2005 05:22:55 -0800, makko said to the parser:

    > anyone know how to writre a program that take a commandline formula and
    > prints the calculated result? example; $program 1+(2x3(3/2))-8


    Yes.

    Parsing mathematical expressions is pretty standard 1st or 2nd year
    comp. sci. fare, which is likely where you were given this assignment...

    Bang away at it and then post your c ode here if you've got specific
    issues. No one's going to sit down and write it for you.


    Michael
     
    Michael Coyne, Jan 21, 2005
    #4
  5. makko wrote:
    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8


    Yes.
    If you want to steal one, get the freely available source to 'bc'.
    And this is not a question about C, so is off-topic here.
     
    Martin Ambuhl, Jan 21, 2005
    #5
  6. makko

    CBFalconer Guest

    makko wrote:
    >
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8


    Yes.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Jan 21, 2005
    #6
  7. In article <>,
    makko <> wrote:

    >anyone know how to writre a program that take a commandline formula
    >and prints the calculated result? example;
    >$program 1+(2x3(3/2))-8


    Unlike some languages, C does not have an "eval" function. So you
    will just have to write code to parse and evaluate the expression.
    Representing the parsed expressions is a fairly standard problem in
    the use of structures. The difficult part is parsing, but C has a
    long history of parser-generators many of which are freely available.
    Search for "bison" for example.

    -- Richard
     
    Richard Tobin, Jan 21, 2005
    #7
  8. makko wrote:
    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8
    >
    > reagrds;
    > Makkko
    >


    The interesting part is the kind of data structure
    you will use. Are you going to use a stack, queue,
    or binary tree? What data structures are you allowed
    to use?

    If you just need a calculator program, there are free
    ones available that do a better job.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.comeaucomputing.com/learn/faq/
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
    http://www.sgi.com/tech/stl -- Standard Template Library
     
    Thomas Matthews, Jan 21, 2005
    #8
  9. makko

    Ben Pfaff Guest

    Thomas Matthews <> writes:

    > makko wrote:
    >> anyone know how to writre a program that take a commandline formula
    >> and prints the calculated result? example;
    >> $program 1+(2x3(3/2))-8

    >
    > The interesting part is the kind of data structure
    > you will use. Are you going to use a stack, queue,
    > or binary tree? What data structures are you allowed
    > to use?


    If you just want to evaluate a formula, there's no need for any
    of those data structures, as long as you're allowed to use
    recursion.
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Jan 21, 2005
    #9
  10. makko wrote:
    >
    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8
    >
    > reagrds;
    > Makkko


    Yes.

    I have done it in several languages (not C). Kruse's book "Data Structures and
    Program Design" develops a tree-based parser in Pascal. I don't recall whether
    or not it is recursive descent, but I don't think so.

    My own formula parsers were all recursive descent and used a stack of pointers
    into the input string, rather than a parse tree. So it was easy enough to
    do it that way. (I am no guru: if I could, you can.)

    One thing I hope you have mastered already is RPN ("reverse Polish") or postfix
    notation; you should understand why you need to rearrange an algebraic formula
    into this form before you can evaluate it.

    You might also look at the "dragon book" (Alfred V. Aho, Ravi Sethi, Jeffrey
    D. Ullman, "Compilers: principles, techniques, and tools"). They discuss some
    important aspects of compiler design and rule-based programs in general, in
    particular the BNF notation for expressing rules. If you can state the rules
    for your formula evaluator in BNF you will see why recursion is a natural
    way to program it.

    OTOH, you can do it with "Operator Precedence Grammar" (look it up!), which
    might lead to a slightly simpler program.

    Once you have done the reading part of your HW, you can tackle the
    programming part. I suggest you look into FINITE STATE MACHINES because
    that is the easiest way to program pattern-recognition subroutines.

    Test the program in bite-sized pieces, i.e. make sure the parser part can
    recognize the parts of your formula (terms, factors, operators, functions,
    constants, variables, arrays, whatever). Only after that is working should
    you decide what to do with the pieces. It would be a good idea to include
    diagnostic code while you construct the program--for example something that
    will display the current state of the parse tree (if you decide on a tree) or
    the expression stack (if you use that), as you decompose the input into
    its parts.

    If you run into difficulties with C, the folks in this group will help you out,
    as I can attest from personal experience. But they really have little interest
    in doing your HW for you.

    --
    Julian V. Noble
    Professor Emeritus of Physics

    ^^^^^^^^^^^^^^^^^^
    http://galileo.phys.virginia.edu/~jvn/

    "As democracy is perfected, the office of president represents, more and
    more closely, the inner soul of the people. On some great and glorious
    day the plain folks of the land will reach their heart's desire at last
    and the White House will be adorned by a downright moron."

    --- H. L. Mencken (1880 - 1956)
     
    Julian V. Noble, Jan 21, 2005
    #10
  11. Ben Pfaff wrote:
    >>> anyone know how to writre a program that take a commandline formula
    >>> and prints the calculated result? example;
    >>> $program 1+(2x3(3/2))-8

    >>
    >> The interesting part is the kind of data structure
    >> you will use. Are you going to use a stack, queue,
    >> or binary tree? What data structures are you allowed
    >> to use?

    >
    > If you just want to evaluate a formula, there's no need for any
    > of those data structures, as long as you're allowed to use
    > recursion.


    This depend on what you understand under "recursion". Normally, at the
    algorithmical level recursion does require a supporting stack-like
    structure by definition.

    If you are taking about simple implementation-level recursion (i.e.
    syntactical recursion) then you are right, there's no need for an
    explicit stack. Although one might argue that this doesn't change much,
    since "stack" is just an abstract data handling approach (LIFO) and in
    this sense syntactical recursion still uses "stack".

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Jan 21, 2005
    #11
  12. makko wrote:
    >
    > Hello,
    > anyone know how to writre a program that take a commandline formula
    > and prints the calculated result? example;
    > $program 1+(2x3(3/2))-8


    Replace interesting with trivial.

    There is an 100 line example of how to do this in the
    GNU Flex and GNU Bison documentation.

    http://www.gnu.org/software/bison/

    Erik
    --
    +-----------------------------------------------------------+
    Erik de Castro Lopo (Yes it's valid)
    +-----------------------------------------------------------+
    "Whenever the C++ language designers had two competing ideas as to
    how they should solve some problem, they said, "OK, we'll do them
    both". So the language is too baroque for my taste." -- Donald E Knuth
     
    Erik de Castro Lopo, Jan 21, 2005
    #12
  13. makko

    Mabden Guest

    "CBFalconer" <> wrote in message
    news:...
    > makko wrote:
    > >
    > > anyone know how to writre a program that take a commandline formula
    > > and prints the calculated result? example;
    > > $program 1+(2x3(3/2))-8

    >
    > Yes.


    You attack the problem quickly, Falconer!

    First, one must define what "writre" means...

    --
    Mabden
     
    Mabden, Jan 23, 2005
    #13
  14. On Fri, 21 Jan 2005 11:31:57 -0800, Andrey Tarasevich wrote:

    > Ben Pfaff wrote:
    >>>> anyone know how to writre a program that take a commandline formula
    >>>> and prints the calculated result? example;
    >>>> $program 1+(2x3(3/2))-8
    >>>
    >>> The interesting part is the kind of data structure
    >>> you will use. Are you going to use a stack, queue,
    >>> or binary tree? What data structures are you allowed
    >>> to use?

    >>
    >> If you just want to evaluate a formula, there's no need for any
    >> of those data structures, as long as you're allowed to use
    >> recursion.

    >
    > This depend on what you understand under "recursion".


    In the context of C that is very clear, it is the ability of a function ot
    call itself (directly or indirectly).

    > Normally, at the
    > algorithmical level recursion does require a supporting stack-like
    > structure by definition.


    That is an implementation detail. The language provides an abstraction
    that does not require knowledge of such details. It isn't something that
    the programmer need be concerned about.

    > If you are taking about simple implementation-level recursion (i.e.
    > syntactical recursion) then you are right, there's no need for an
    > explicit stack. Although one might argue that this doesn't change much,
    > since "stack" is just an abstract data handling approach (LIFO) and in
    > this sense syntactical recursion still uses "stack".


    Again the implementation details are hidden, the programmer doesn't have
    to worry at that level.

    Lawrence
     
    Lawrence Kirby, Jan 24, 2005
    #14
  15. makko

    makko Guest

    I got a parser from Phil Howard's libh, thanx yall for your help :)


    //-----------------------------------------------------------------------------
    // Copyright © 2004 - Philip Howard - All rights reserved
    //
    // This program is free software; you can redistribute it and/or
    // modify it under the terms of the GNU General Public License
    // as published by the Free Software Foundation; either version 2
    // of the License, or (at your option) any later version.
    //
    // This program is distributed in the hope that it will be useful,
    // but WITHOUT ANY WARRANTY; without even the implied warranty of
    // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    // GNU General Public License for more details.
    //
    // You should have received a copy of the GNU General Public License
    // along with this program; if not, write to the Free Software
    // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
    02111-1307, USA.
    //-----------------------------------------------------------------------------
    // package libh/string
    // homepage http://libh.slashusr.org/
    //-----------------------------------------------------------------------------
    // author Philip Howard
    // email libh at ipal dot org
    // homepage http://phil.ipal.org/
    //-----------------------------------------------------------------------------
    // This file is best viewed using a fixed spaced font such as Courier
    // and in a display at least 120 columns wide.
    //-----------------------------------------------------------------------------

    #include <math.h>
    #include <errno.h>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>

    //-----------------------------------------------------------------------------
    // function str_expr_to_d
    //
    // purpose Convert a string containing a numeric expression into a
    // double.
    //
    // arguments 1 (const char *) pointer to string to convert
    // 2 (char * *) pointer to string to store end pointer
    //
    // returns (double) converted result
    //
    // note Numeric values that exceed the maximums for this data type
    // will result in undefined values being returned.
    //-----------------------------------------------------------------------------
    double
    str_expr_to_d (
    const char * arg_str
    ,
    char * * arg_end_ptr
    )
    {
    struct stack_node {
    double value ;
    int level ;
    int oper ;
    };

    struct stack_node stack_array [64];
    struct stack_node * stack_top ;
    struct stack_node * stack_end ;

    double number ;
    char * str_ptr ;
    char * end_ptr ;
    int erange ;
    int nest ;
    int op_code ;
    int op_level ;


    stack_top = stack_array;
    stack_top->level = 0;

    stack_end = stack_array + 64;

    erange = 0;
    nest = 0;
    op_level = 0;

    * (const char * *) & str_ptr = arg_str;

    for (;;) {

    //--------------------
    // Expecting a number.
    //--------------------

    //-- Check for end of string.
    if ( * str_ptr == 0 ) {
    errno = EINVAL;
    number = 0.0;
    break;
    }

    //-- Check for spaces.
    if ( isspace( * str_ptr ) ) {
    ++ str_ptr;
    continue;
    }

    //-- Check for nesting.
    if ( * str_ptr == '(' ) {
    nest += 8;
    ++ str_ptr;
    continue;
    }

    //-- Convert a number.
    errno = 0;
    end_ptr = NULL;
    number = strtod( str_ptr, & end_ptr );
    if ( ! end_ptr ) {
    errno = EINVAL;
    number = 0.0;
    break;
    }
    if ( errno == ERANGE ) {
    ++ erange;
    }
    str_ptr = end_ptr;

    //-----------------------
    // Expecting an operator.
    //-----------------------

    //-- Get the operator code.
    for (;;) {
    op_code = * str_ptr ++;

    //-- Skip spaces.
    if ( isspace( op_code ) ) {
    continue;
    }

    //-- Check for unnesting.
    if ( op_code == ')' && nest >= 8 ) {
    nest -= 8;
    continue;
    }

    //-- Operator or not, go with it.
    break;
    }

    //-- Determine level of this operator.
    op_level = 0;
    if ( op_code == '+' || op_code == '-' ) {
    op_level = nest + 2;
    }
    else if ( op_code == '*' || op_code == '/' ) {
    op_level = nest + 3;
    }
    else if ( op_code == '^' ) {
    op_level = nest + 4;
    }

    //-- Do stacked arithmetic.
    while ( stack_top->level > op_level ) {
    if ( stack_top->oper == '+' ) {
    number = stack_top->value + number;
    }
    else if ( stack_top->oper == '-' ) {
    number = stack_top->value - number;
    }
    else if ( stack_top->oper == '*' ) {
    number = stack_top->value * number;
    }
    else if ( stack_top->oper == '/' ) {
    number = stack_top->value / number;
    }
    else if ( stack_top->oper == '^' ) {
    number = pow( stack_top->value, number );
    }
    if ( -- stack_top < stack_array ) break;
    }

    //-- If end of expression.
    if ( op_level == 0 ) {
    -- str_ptr;
    if ( nest > 0 ) {
    errno = EINVAL;
    number = 0.0;
    }
    break;
    }

    //-- Push the new operator into the stack.
    if ( ++ stack_top >= stack_end ) {
    errno = ENOBUFS;
    number = 0.0;
    break;
    }
    stack_top->value = number;
    stack_top->oper = op_code;
    stack_top->level = op_level;
    }

    if ( arg_end_ptr ) * arg_end_ptr = str_ptr;
    return number;
    }

    int main(int argc,char *argv[])
    {
    system("clear");
    if(argc != 2)
    {
    printf("\nEnter the operands surrouded in quotes, ");
    printf("eg '1+2(2-6)'\n\n");
    exit(1);
    }
    double d = str_expr_to_d(argv[1],NULL);
    printf("%f\n",d);
    return 0;
    }

    EOF
     
    makko, Jan 25, 2005
    #15
  16. makko

    CBFalconer Guest

    makko wrote:
    >
    > I got a parser from Phil Howard's libh, thanx yall for your help :)
    >
    > //--------------------------------------------------------------
    > // Copyright © 2004 - Philip Howard - All rights reserved
    > //

    .... snip license ...
    > //--------------------------------------------------------------
    > // package libh/string
    > // homepage http://libh.slashusr.org/
    > //--------------------------------------------------------------
    > // author Philip Howard
    > // email libh at ipal dot org
    > // homepage http://phil.ipal.org/


    .... snip code ...

    This code has some problems, even beyond the use of // comments
    (which make it impossible to compile with -pedantic). One is the
    use of ENOBUFS (and possibly others undefined in standard C). When
    run it fails to detect the input error in the example prompt.

    It is not c.l.c. portable quality. It was probably never intended
    to be so, so this is no reflection on Mr. Howard, who did not
    publish it here. Just a warning to prospective users.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
     
    CBFalconer, Jan 25, 2005
    #16
  17. makko

    dandelion Guest

    "Lawrence Kirby" <> wrote in message
    news:p...
    <snip>

    > Again the implementation details are hidden, the programmer doesn't have
    > to worry at that level.


    Untill you screw the CPU-stack, that is.
     
    dandelion, Jan 25, 2005
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Elliot M. Rodriguez

    An interesting problem

    Elliot M. Rodriguez, Oct 21, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    392
    Elliot M. Rodriguez
    Oct 21, 2003
  2. Bilbo
    Replies:
    3
    Views:
    427
    Bilbo
    Nov 20, 2003
  3. francois
    Replies:
    0
    Views:
    377
    francois
    Jan 9, 2004
  4. Rakesh Roberts

    A Very interesting cookie problem

    Rakesh Roberts, Apr 7, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    472
    Craig Deelsnyder
    Apr 7, 2004
  5. Xaonon
    Replies:
    1
    Views:
    375
    Matt Humphrey
    Dec 17, 2003
Loading...

Share This Page