Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using...
Algorithm for converting infix to postfix notation
1. Initialize an empty stack and an empty output string.
2. Scan the infix expression from left to right.
3. If the current element is an operand, append it to the output string.
4. If the current element is an operator, then:
a. Pop operators from the stack until an operator with lower precedence than the current operator is found, and append them to the output string.
b. Push the current operator onto the stack.
5. If the current element is a left parenthesis, push it onto the stack.
6. If the current element is a right parenthesis, then:
a. Pop operators from the stack and append them to the output string until a left parenthesis is found.
b. Discard the left parenthesis from the stack.
7. Repeat steps 3 to 6 until all elements have been scanned.
8. Pop any remaining operators from the stack and append them to the output string.
Maximum number of symbols on the stack
In the given infix expression, the maximum number of symbols on the stack at one time can be calculated as follows:
1. Initialize an empty stack.
2. Scan the infix expression from left to right.
3. Keep track of the maximum size of the stack during the scan.
4. If the current element is an operand, do not push anything onto the stack.
5. If the current element is an operator or a parenthesis, push it onto the stack.
6. If the current element is a right parenthesis, pop all elements from the stack until a left parenthesis is found and count the number of symbols popped.
7. Update the maximum size of the stack if it is greater than the previous maximum.
8. After scanning the entire expression, return the maximum size of the stack.
For the given infix expression, the maximum size of the stack can be calculated as follows:
1. Initialize an empty stack and a variable to keep track of the maximum size.
2. Scan the infix expression from left to right.
3. The first element is 4, an operand. Do not push anything onto the stack.
4. The next element is 3, an operand. Do not push anything onto the stack.
5. The next element is *, an operator. Push it onto the stack.
6. The next element is (, a left parenthesis. Push it onto the stack.
7. The next element is 6, an operand. Do not push anything onto the stack.
8. The next element is *, an operator. Push it onto the stack.
9. The next element is 3, an operand. Do not push anything onto the stack.
10. The next element is -, an operator. Push it onto the stack.
11. The next element is 12, an operand. Do not push anything onto the stack.
12. The next element is ), a right parenthesis. Pop all elements from the stack until a left parenthesis is found. The symbols popped are - * 6 3. The size of the stack is 1 after the left parenthesis is discarded.
13. Update the maximum size of the stack to 4.
14. The last element is . Do not push anything onto the stack.
15. Return the maximum size of the stack, which is 4.
Therefore, the correct answer is option D, 4.
Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using...
When we perform the conversion from infix to postfix expression +, *, (, * symbols are placed inside the stack. A maximum of 4 symbols are identified during the entire conversion.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).