On Jul 11, 9:58 am, amit <amitjaspal...@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.