Evaluate postfix expression
Hard
Java
Methods
19 views
Problem Statement
Task: evaluate postfix expression given as int tokens and ops codes. Use stack.
Input Format
First line: Integer n (number of tokens)
Second line: n space-separated tokens (integers and operators)
Operators can be: +, -, *, /
Second line: n space-separated tokens (integers and operators)
Operators can be: +, -, *, /
Output Format
Print one integer: the result of the postfix expression
Example
5 2 3 1 * +
123
Constraints
• 1 ≤ n ≤ 100
• Tokens are valid integers or operators
• Division is integer division
• The postfix expression is valid
• Tokens are valid integers or operators
• Division is integer division
• The postfix expression is valid
Concept Explanation
Postfix expression: 2 3 1 * +
Step-by-step evaluation:
• Push 2
• Push 3
• Push 1
• * → 3 × 1 = 3 → push 3
• + → 2 + 3 = 5
Final result = 5
Step-by-step evaluation:
• Push 2
• Push 3
• Push 1
• * → 3 × 1 = 3 → push 3
• + → 2 + 3 = 5
Final result = 5
Step-by-Step Explanation
1.Create a Stack.
2.Traverse all tokens.
3.If token is a number → push into stack.
4.If token is an operator:
• Pop two numbers from stack (operand2 and operand1).
• Perform operation: operand1 operator operand2.
• Push result back to stack.
5.After processing all tokens, the stack will contain one value.
6.Print that value.
2.Traverse all tokens.
3.If token is a number → push into stack.
4.If token is an operator:
• Pop two numbers from stack (operand2 and operand1).
• Perform operation: operand1 operator operand2.
• Push result back to stack.
5.After processing all tokens, the stack will contain one value.
6.Print that value.
Concept Explanation
Postfix expression: 2 3 1 * +
Step-by-step evaluation:
• Push 2
• Push 3
• Push 1
• * → 3 × 1 = 3 → push 3
• + → 2 + 3 = 5
Final result = 5
Step-by-step evaluation:
• Push 2
• Push 3
• Push 1
• * → 3 × 1 = 3 → push 3
• + → 2 + 3 = 5
Final result = 5
Step-by-Step Explanation
1.Create a Stack.
2.Traverse all tokens.
3.If token is a number → push into stack.
4.If token is an operator:
• Pop two numbers from stack (operand2 and operand1).
• Perform operation: operand1 operator operand2.
• Push result back to stack.
5.After processing all tokens, the stack will contain one value.
6.Print that value.
2.Traverse all tokens.
3.If token is a number → push into stack.
4.If token is an operator:
• Pop two numbers from stack (operand2 and operand1).
• Perform operation: operand1 operator operand2.
• Push result back to stack.
5.After processing all tokens, the stack will contain one value.
6.Print that value.
Input / Output Format
Input Format
First line: Integer n (number of tokens)
Second line: n space-separated tokens (integers and operators)
Operators can be: +, -, *, /
Second line: n space-separated tokens (integers and operators)
Operators can be: +, -, *, /
Output Format
Print one integer: the result of the postfix expression
Constraints
• 1 ≤ n ≤ 100
• Tokens are valid integers or operators
• Division is integer division
• The postfix expression is valid
• Tokens are valid integers or operators
• Division is integer division
• The postfix expression is valid
Examples
Input:
5
2 3 1 * +
Output:
123
Example Solution (Public)
static int evalPostfix(int[] t){java.util.ArrayDeque<Integer> st=new java.util.ArrayDeque<>();for(int x:t){if(x>=0){st.push(x);}else{int b=st.pop(),a=st.pop();int r=0; if(x==-1) r=a+b; else if(x==-2) r=a-b; else if(x==-3) r=a*b; else r=a/b; st.push(r);} }return st.pop();}
Official Solution Code
static int evalPostfix(int[] t){java.util.ArrayDeque<Integer> st=new java.util.ArrayDeque<>();for(int x:t){if(x>=0){st.push(x);}else{int b=st.pop(),a=st.pop();int r=0; if(x==-1) r=a+b; else if(x==-2) r=a-b; else if(x==-3) r=a*b; else r=a/b; st.push(r);} }return st.pop();}
Please login to submit solutions.