Scribd
Upload
10 views2 pages

Stack

The document explains mathematical notations used in computer science, focusing on Infix, Prefix, and Postfix notations, with Postfix being the most efficient for stack processing. It outlines common algorithms for evaluating Postfix expressions and converting Infix to Postfix, including the stack method and the shunting-yard algorithm. A comparison table highlights the features and complexities of each notation, along with a C++ implementation tip for handling non-commutative operations.

Uploaded by

Sakrit Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Stack

The document explains mathematical notations used in computer science, focusing on Infix, Prefix, and Postfix notations, with Postfix being the most efficient for stack processing. It outlines common algorithms for evaluating Postfix expressions and converting Infix to Postfix, including the stack method and the shunting-yard algorithm. A comparison table highlights the features and complexities of each notation, along with a C++ implementation tip for handling non-commutative operations.

Uploaded by

Sakrit Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Concept Overview
In computer science, these notations describe how we write mathematical expressions.
While humans prefer Infix, computers find Postfix and Prefix much easier to evaluate
because they don't require parentheses to define order of operations.

Infix Notation
Structure: Operand1 Operator Operand2 (e.g., 3 + 4 )
Characteristics: Uses operator precedence (PEMDAS/BODMAS) and parentheses.
LeetCode Use: Usually the format of the input string in "Calculator" problems.

Prefix Notation (Polish Notation)


Structure: Operator Operand1 Operand2 (e.g., + 3 4 )
Characteristics: Scanned from right to left for stack evaluation.
LeetCode Use: Less common, but appearing in some expression tree transformation
problems.

Postfix Notation (Reverse Polish Notation - RPN)


Structure: Operand1 Operand2 Operator (e.g., 3 4 + )
Characteristics: Scanned from left to right. No parentheses needed.
LeetCode Use: Extremely High. This is the most efficient format for stack processing.

2. Common LeetCode Algorithms


A. Evaluating Postfix (The Stack Method)
This is the logic used for LeetCode 150: Evaluate Reverse Polish Notation.

1. Initialize an empty stack.


2. Scan the expression from left to right.
3. If the element is a number, push it to the stack.
4. If the element is an operator:
pop() the top element (this is Operand 2 ).
pop() the next element (this is Operand 1 ).
Apply the operator: Operand 1 [op] Operand 2 .
push() the result back onto the stack.

B. Converting Infix to Postfix (Shunting-Yard)


Used for complex calculators like LeetCode 772: Basic Calculator III.

Rule: Maintain a stack for operators and a list/string for the output.
Precedence: If the current operator has lower or equal precedence than the one on top
of the stack, pop the stack to the output before pushing the new operator.

3. Quick Comparison Table

Feature Infix Prefix Postfix (RPN)


Human Readable Yes No No
Stack Scan Direction N/A (requires parsing) Right → Left Left → Right
Complexity High (needs recursion/rules) Low Lowest
Example (A + B) * C * + A B C A B + C *

4. C++ Implementation Tip


When dealing with these in C++, always remember that for non-commutative operations
(subtraction and division), the first pop is the divisor/subtrahend.

C++

// C++ snippet for Postfix evaluation logic


int op2 = [Link](); [Link](); // The second operand
int op1 = [Link](); [Link](); // The first operand

if (token == "-") [Link](op1 - op2);


else if (token == "/") [Link](op1 / op2);

You might also like