Solved

# insert parentheses to an arithmetic expression

Posted on 2004-10-31
272 Views
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

LVL 55

Expert Comment

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

(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

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 ()
{
}

{
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

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

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

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

....
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

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

## Featured Post

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.