Interview Questions And Answers 
-
How to remove extra bracket from expressions,i.e ((((A+B))*C))?
most optimized answer??8,073 Views |
(25 votes, avg: 3.64)
Loading ...
Answers »
Our Sponsors
Our Sponsors
How to remove extra bracket from expressions,i.e ((((A+B))*C))?
most optimized answer??
8,073 Views | (25 votes, avg: 3.64)
Loading ...
Push one after the other in a stack. The last ones remaining either in the stack(opening brackets) or in the input buffer(closing brackets) are the extra brackets which should be removed. When the next symbol in the input buffer is ‘)’ pop a corresponding ‘(’ from the stack.
Regards,
J1gs4w
1.Use an array or a pointer to the string to store the input expression.
2.start scanning frfom the left.
3.on encountering ( push its index into a stack.
4.on encountering ) pop an index out of the stack.
5.omit all other values like A ,+, B,etc.
6.after the input is exhausted if the stack is not empy delete the braces present at the indices in the stack.
1.use one operator stack to store the operators ,
2.whenever u find a closed bracket just pop the operator and
if the stack is empty then delete the closed bracket and also the opening bracket correspond to that…
3. at the end if there is any operator in the stack then we can conclude that there is no proper brackets included.
Huh? (A+B)*C is already as optimized as it can be. Addition is implemented as a single clock cycle operation, whereas multiplication generally takes multiple clock cycles in the ALU. Factoring the expression into (A*C)+(B*C) would take more time to calculate than the original expression. Hence: huh?
use Stack to remove extra bracket.
e.g. if there is no operator between the opening bracket and closing bracket than that braket need to be removed.
insert the OB (open brace) into a queue.
remove the OB from the queue for every CB (closed brace)
if the expression has reached the end and if the queue is not empty then remove the no of OB found in the queue from the expression from the front side.
And if the queue is empty and the expression still has CB then remove the remaining CB from the expression.
If i am not wrong, the queation asked is not to match the braces but to remove extra ones whose removal would not make a difference. Here ((((A+b))*c)) should be made to (A+b)*c .
1) Keep pushing all variables onto the stack.When u encounter an ‘)’, pop the next variable.If it is a ‘(’,do not add these two to the resultant string else
keep popping all the variables till one ‘(’ has been encounteres and keep adding it in reverse order to the resultant string.
#include
#include
#include
#include
using namespace std;
void put_brace(string &p)
{
p+=’)';
p=’('+p;
}
int main()
{
stack s;
string input, result=”",res=”";
cin>>input;
int i;
for(i=0;i
What about trying converting a string to postfix notation which will remove braces.
converting the postfix string to infix string again.
Will the stack idea work?
What if the expression was ((A+B)+C() in which case there is the extra ( in the 9th position?
Using the push pop idea we would push the index 0, push the index 1, hit the first ) and pop the index 1 out, hit the last ( and push the index 8, then pop that one out leaving the index 0. However that isn’t the one we want to remove.
1. Make two arrays and a count variable.
2. First array is to store indexes of opening braces
3. Second arrays is to keep track that corresponding brace in first array is essential for truthfulness of original expression.
4. Start Scan the expression. Do the following
i. When ever opening brace is encountered, add its index into first array and in second array mention that this brace is not necessary(e.g. by putting 0). Increment count.
ii. When closing brace is encountered and
a. Count is 0: means that there is mismatch in the bracket structure so delete the closing brace
b. Check 2nd array if this brace pair is necessary. if not delete the pair otherwise remove the entry from both arrays. Decrement the count.
iii. When char is neither opening or closing brace then it must be some operator or variable. Mark the last added brace as essential.
4. If at the end of expression there are still some opening braces left in first array it means there are extra opening braces. So remove them.
Leave an Answer/Comment