On Jul 11, 9:58 am, amit <[email protected]> wrote:
> Give a algorithm to remove extra pair of parenthesis
> Remove unnecessary from an expression :
> 1) (((a))) => a
> 2) (a+b) => a+b
> 3) (a+b)*c => (a+b)*c
> 4)(((a+b)*(c+d))+e) => (a+b)*(c+d)+e
We can build an abstract syntax tree with a simple parser and then
walk the tree to print out the expression with only the parentheses
that are really needed. If we assume both + and * are associative,
this is very easy: The only case where we need parens is when a +
occurs as either the left or right child of a *.
The problem gets more interesting with - and / because e.g. although
1+2+3 = 1+(2+3), it is not true that 1-2-3 = 1-(2-3). I'll leave this
to you.
So here you go:
#include <stdio.h>
#include <stdlib.h>
// Current character.
int ch;
// Very simple scanner.
#define SCAN do ch = getchar(); while (ch == ' ')
// Abstract syntax tree node.
typedef struct node_s {
int op;
struct node_s *lhs, *rhs;
} NODE;
// Allocate a new node.
NODE *new(int op, NODE *lhs, NODE *rhs)
{
NODE *r = malloc(sizeof *r);
r->op = op; r->lhs = lhs; r->rhs = rhs;
return r;
}
// Simple recursive descent parser builds syntax tree.
NODE *expr(void);
NODE *term(void);
NODE *factor(void);
NODE *line(void)
{
NODE *r = expr();
if (ch != '\n') {
fprintf(stderr, "junk after expr\n");
exit(1);
}
return r;
}
NODE *expr(void)
{
NODE *r = term();
while (ch == '+') {
SCAN;
r = new('+', r, term());
}
return r;
}
NODE *term(void)
{
NODE *r = factor();
while (ch == '*') {
SCAN;
r = new('*', r, factor());
}
return r;
}
NODE *factor(void)
{
NODE *r = 0;
if (ch == '(') {
SCAN;
r = expr();
if (ch != ')') {
fprintf(stderr, "missing )\n");
exit(1);
}
SCAN;
}
else {
r = new(ch, 0, 0);
SCAN;
}
return r;
}
// Tree walker prints simplified expression.
void print(NODE *expr);
void parenthesize(int parent, NODE *expr)
{
if (parent == '*' && expr->op == '+') printf("(");
print(expr);
if (parent == '*' && expr->op == '+') printf(")");
}
void print(NODE *expr)
{
if (expr->lhs == 0) // leaf node
printf("%c", expr->op);
else {
parenthesize(expr->op, expr->lhs);
printf("%c", expr->op);
parenthesize(expr->op, expr->rhs);
}
}
// Parse one expression per line and print simplified form.
int main(void)
{
while (1) {
SCAN;
if (ch == EOF) return 0;
print(line());
printf("\n");
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
