Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# insert parentheses to an arithmetic expression

Posted on 2004-10-26
Medium Priority
819 Views
how do I insert parentheses to an arithmetic expression in order of execution for C programming?
0
Question by:Ofakile1
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 3
• 2

Author Comment

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

LVL 46

Expert Comment

ID: 12417556
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

ID: 12422372
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

ID: 12434042
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

ID: 12434135
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

ID: 12434231
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

ID: 12434398
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 46

Accepted Solution

Kent Olsen earned 60 total points
ID: 12436777
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

ID: 12456963
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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ā¦
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 opening and reading files 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.
###### Suggested Courses
Course of the Month10 days, 19 hours left to enroll