insert parentheses to an arithmetic expression

how do I insert parentheses to an arithmetic expression in order of execution for C programming?
Ofakile1Asked:
Who is Participating?
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
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
 
Ofakile1Author Commented:
how do I insert parentheses to an arithmetic expression in order of execution for C programming?
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Ofakile1,

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



Kent
0
Live webcast with Pinal Dave

Pinal Dave will teach you tricks to help identify the real root cause of database problems rather than red herrings. Attendees will learn scripts that they can use in their environment to immediately figure out their performance Blame Shifters and fix them quickly.

 
PaulCaswellCommented:
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
 
Ofakile1Author Commented:
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
 
PaulCaswellCommented:
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
 
Ofakile1Author Commented:
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
 
PaulCaswellCommented:
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
 
Ofakile1Author Commented:
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
All Courses

From novice to tech pro — start learning today.