Solved

insert parentheses to an arithmetic expression

Posted on 2004-10-26
688 Views
Last Modified: 2011-09-20
how do I insert parentheses to an arithmetic expression in order of execution for C programming?
0
Question by:Ofakile1
    9 Comments
     

    Author Comment

    by:Ofakile1
    how do I insert parentheses to an arithmetic expression in order of execution for C programming?
    0
     
    LVL 45

    Expert Comment

    by:Kdo
    Hi Ofakile1,

    Build the expression as a tree, then traverse the tree, writing the expression with the proper parentheses.



    Kent
    0
     
    LVL 16

    Expert Comment

    by:PaulCaswell
    1. Read Kernighan & Ritchie on C expression evaluation. I think they have some examples with parenthesis added.
    2. Try to do your homework first, then, if you get stuck, it is easier to help.

    Paul
    0
     

    Author Comment

    by:Ofakile1
    My actual question was. Lets say I have a user inputs an arithmetic expression: 5+3/-2. Once this expression is entered. the output is suppost to look like this:

    5+3/(-2)
    5+(3/(-2))
    (5+(3/(-2)))



    That is where I am stuck on. How will I set un an array that will shift the values left or right so that parentheses can be entered according to what the arithmetic sign is?
    0
     
    LVL 16

    Expert Comment

    by:PaulCaswell
    This is a complex question. The problem arises when, for example, you are given stuff like:

    5++3/-2*(-1-3+4)

    You need to do the following:

    1. Decide how much of the C syntax you want to emulate.
    2.a. If not too much, emulate it with a state machine.
    2.b. If almost all, define your syntax in BNF and find a generic BNF parser.

    Paul
    0
     

    Author Comment

    by:Ofakile1
    Also, here is what I came up with so far with my program. Sorry I forgot to post it earlier. When I tried to run it to see if the program at list show parenthesis, it said "Segmentation fault". What should I do to fix it??




    #include <stdio.h>

    #define MLOE 20

    int main()

    {
    char a[40];
     int i, j;
     char operator1= '-', operator2 = '+',operator3 = '*',operator4 = '/';

    printf("-------------------------------------------------------------------\n");
    printf("          Welcome to the Arithmetic Expression Evaluator!       \n ");
    printf("-------------------------------------------------------------------\n");
    printf("     Give me an arithmetic expression and I will insert the        \n");
    printf("     appropriate parentheses per the C language's arithmetic      \n");
    printf("     operator precedence and associativity rules.                \n  ");


    printf("Expression:\n");


    int count=0;

    for(i=0; i<20; i++)
    {
     scanf("%c", a[i]);
     count++;
    }
    for(i=1; i<count; i=i+2)
    {
     if(a[i]!=operator1 && a[i] !=operator2 && a[i] !=operator3 && a[i] !=operator4)
    {
     for(j = count + 1; j == i; j--)
    {
     a[j] = a[j- 2];
    }
    a[i+2] = ')';
    a[i+1] = a[i];
    a[i] = a[i-1];
    a[i-1] = '(';

    }
    }
    return 0;
    }


    0
     
    LVL 16

    Expert Comment

    by:PaulCaswell
    Although I am not sure whether your parser is correct, I can now understand why you had a problem.

    To insert a character into a string 'a' of length 'count' at position 'i' use:

    memmove(&a[i+1], &a[i], count - i);
    count += 1;

    Paul
    0
     
    LVL 45

    Accepted Solution

    by:
    Hi Ofakile1,

    This goes back to my original suggestion about building a tree from the expression and traversing the tree.  There are countless descriptions and programs on the web that will tell you how to build the tree (or even do it for you).

    The general theory is this:  If a node is an end-node, it is an operand.  If the node has two children, it is a binary operator (+-/*).  If the node has one child, it is a unary operator (-).

    The simple equation:  A+B+C  has several possible trees.  One of them is:

            +             root  (node 0)
          /   \
        +     C          nodes 1, 2
      /   \
    A      B             nodes 3, 4


    Traverse (NODE *node)
    {
      if (node->LeftChild || node->RightChild)  /*  Node is an operator node  */
      {
        printf ("("));
        if (node->LeftChild)
          Traverse (node->LeftChild);
        printf (node->operator);
        Traverse (node->RightChild);
        printf (")");
      }
      else
        printf (node->VariableName);
    }

    Calling this function on the root node, the following processes occur:

    Node   Contents   Action(s)
    root          +            Print (
                                 Traverse (LeftChild)
    1              +            Print (
                                 Traverse (LeftChild)
    3              A            Print A
    1                            Print +
                                 Traverse (RightChild)
    4              B            Print B
    1                            Print )
    root                        Print +
                                 Traverse (RightChild)
    2              C            Print C
    root                        Print )

    Following the sequence of print statements, what is output is:

    ((A+B)+C)


    Kent

    0
     

    Author Comment

    by:Ofakile1
    Thanx very much for all the suggestion. I rewrote the program and tried to make it work but it doesn't run properly. This the program below:

    #include <stdio.h>

    #define SIZE 20

    int main()

    {
     int i = 0 ;
     int a[SIZE];
     int b[40];
     int inext =i + 1;
     char operator1= '-', operator2 = '+',operator3 = '*',operator4 = '/';



    printf("-------------------------------------------------------------------\n");
    printf("          Welcome to the Arithmetic Expression Evaluator!       \n ");
    printf("-------------------------------------------------------------------\n");
    printf("     Give me an arithmetic expression and I will insert the        \n");
    printf("     appropriate parentheses per the C language's arithmetic      \n");
    printf("     operator precedence and associativity rules.                \n  ");



    printf("Expression:\n");

    while((a[SIZE]=getchar()): = '\n');

    printf("%d : the size of input.\n", SIZE);

    for(i=0; i<SIZE; i++)
    {
     b[i] = a[i];
    }


    //operator1
    for(i =0; i<SIZE; i++)
    {    if(a[i] == operator1)
    {
          b[0] = '(';
           b[1] = a[i];
             b[2] = a[inext];
               b[3] = ')';

    } // end of if
    printf("%s", a[SIZE]);} // end of for


    //operator2
    for(i =0; i<SIZE; i++)
    {    if(a[i] == operator2)
    {
          b[0] = '(';
           b[1] = a[i];
             b[2] = a[inext];
               b[3] = ')';

    } // end of if
    printf("%s", a[SIZE]);} // end of for

    //operator3
    for(i =0; i<SIZE; i++)
    {    if(a[i] == operator2)
    {
          b[0] = '(';
           b[1] = a[i];
             b[2] = a[inext];
               b[3] = ')';

    } // end of if
    printf("%s", a[SIZE]);} // end of for

    //operator4
    for(i =0; i<SIZE; i++)
    {    if(a[i] == operator2)
    {
          b[0] = '(';
           b[1] = a[i];
             b[2] = a[inext];
               b[3] = ')';

    } // end of if
    printf("%s", a[SIZE]);} // end of for



    printf("\n%c", a[i]);
     if(a[i]!=operator1 && a[i] !=operator2 && a[i] !=operator3 && a[i] !=operator4)
    { ;
    } // end of if
    return 0;
    }
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Suggested Solutions

    Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
    This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
    The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
    The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

    884 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

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now