• Status: Solved
• Priority: Medium
• Security: Public
• Views: 934

# insert parentheses to an arithmetic expression

how do I insert parentheses to an arithmetic expression in order of execution for C programming?
0
Ofakile1
• 4
• 3
• 2
1 Solution

Author Commented:
how do I insert parentheses to an arithmetic expression in order of execution for C programming?
0

Data Warehouse Architect / DBACommented:
Hi Ofakile1,

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

Kent
0

Commented:
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 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

Commented:
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 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

Commented:
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

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

Author 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 4
• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.