Solved

insert parentheses to an arithmetic expression

Posted on 2004-10-31
272 Views
Last Modified: 2010-04-15
I wrote a program that would input a arithmetic expression that would be inputed into an array and a give an output. This how it is suppost to do:
 
Input:
5+3/-2

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


The problem is the program I wrote below doesn't do that?:

#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
Question by:Ofakile1
    8 Comments
     
    LVL 55

    Expert Comment

    by:Jaime Olivares
    This line is very strange. It has lot of errors

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

    I think could be:
    #define MAX_SIZE 20
    int size=0;
    while((a[size++]=getchar()) != '\n' && size<MAX_SIZE);
    printf("%d : the size of input.\n", size);

    0
     
    LVL 55

    Accepted Solution

    by:
    (continues)

    replace all further 'SIZE' with 'size'

    I don't think your code will work at all, there are lots more errors:
    You assume numbers are always 1 digit
    Your inext usage is not legal, just have to use    a[i+1]    instead, I guess.
    You have not considered correctly case where unary minus operator is used
    You have not closed either a or b buffer with a null character before using printf(), this is needed in every C string
    You iterate over original  'a'  buffer again for each operator, so you won't have an incremental result as desired

    Parsing an expression is an advanced topic, I recommend you to read entire basic C Language book before trying it.
    0
     
    LVL 45

    Expert Comment

    by:Kdo
    Hi Ofakile1,

    The problem that you're seeing, is that you're trying to answer a recursive question with a linear answer.


    The basic controls of an expression evaluator are this:

    EvaluateExpression ()
    {
      EvaluateAddSubtract ();
    }

    EvalutateAddSubtract ()
    {
      EvaluateMultDiv ();
      while (parameters[pnum] == '+' || parameters[pnum] == '-')
      {
        if (parameters[pnum] == '+')
          v += EvaluateMultDiv ();
        else
          v -= EvaluateMultDiv ();
      }
      return (v);
    }

    EvaluateMultDiv ()
    {
      EvaluateExp ();
    }

    EvalutateExp ()
    {
    }

    I've inserted the main controls into AddSubtract to show you how these should look.  And this is from an actual evaluator that processes the expression as if it were building a tree, but doesn't actually build the tree.


    Good Luck!
    Kent
    0
     
    LVL 55

    Expert Comment

    by:Jaime Olivares
    Question could be answered with a linear solution, just appending ending parethesis in proper location as you traverses the string buffer, but a helper "insert character" function will be needed.
    0
     
    LVL 22

    Expert Comment

    by:grg99
    I don't see how your program (once all the syntrax errors are fixed) could ever properly parenthesize an expression.

    Where's the information about operator precedence?   You want division to have higher precedence than add or subtract.   I don't see where that is defined.

    What is the result of parenthesizing  a+b+c/d*e+f*g?  

    --------------------
    The simplest way to do this right is to use recursion, anything else involves managing a operator stack or two, not a very transparent algorithm IMHO.






    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    to add to grg999

    How is your program supposed to know from an input of

    5+3/-2

    That I don't want the answer to

    (5+3)/(-2)

    If you are going to work on operator precedence - then why do you need to insert the parenthesis at all? Parenthesis are supposed to be used to modify the natural operator order precedence. If that is the case then without any supplementary information your program will not have a clue with an expression like

    3 * 4 + 3 / 2 + 9 + 5 * 8

    The implied bracketing is
     
    (3*4) + (3/2) + 9 +(5*8) - but any expression parser will evaluate the expression like this without the brackets. Brackets become necessary when we actually want

    3 * (4 + 3/2) + (9 + 5) * 8

    Which will give the correct answer ONLY if the brackets are in place.

    Maybe I haven't understood what you want
    0
     
    LVL 9

    Expert Comment

    by:jhshukla
    ....
    printf("%s", a[SIZE]);} // end of for

    a[SIZE] is a char and you are trying to print it as a string. a horrible mistake. use &a[SIZE] instead.

    and yes, it is better to use a recurvise solution here. it is good to have a tree with opeartors at all non-leaf nodes and operands at leaf nodes.
    outline:
    locate rightmost + or - (binary operator, not unary. this is one of the most difficult tasks)
    if success, split into right and left subexpr and recurse
    else
    locate rightmost * or /
    if success, split into right and left subexpr and recurse
    else /* this is optional */
    locate leftmost ^
    if success, split into right and left subexpr and recurse /* end optional part */
    else
    your expression consist of a single term. return.

    jaydutt
    0
     
    LVL 9

    Expert Comment

    by:jhshukla
    once you have the tree. you can do in-order traversal and put () around subexprs.
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
    An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
    The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
    The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

    875 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

    8 Experts available now in Live!

    Get 1:1 Help Now