Reverse Polish Notation - A Stack Application
Medium L.C. problem: https://leetcode.com/problems/evaluate-reverse-polish-notation/
This is a classic application of Stack. Linear time, linear space. Use of Long just to avoid overflows. Code is below, cheers, ACC.
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are
+
, -
, *
, /
. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
This is a classic application of Stack. Linear time, linear space. Use of Long just to avoid overflows. Code is below, cheers, ACC.
public class Solution { public int EvalRPN(string[] tokens) { Stackstack = new Stack (); foreach (string token in tokens) { string v1 = ""; string v2 = ""; long val = 0; switch (token) { case "+": v1 = stack.Pop(); v2 = stack.Pop(); val = Int64.Parse(v2) + Int64.Parse(v1); stack.Push(val.ToString()); break; case "-": v1 = stack.Pop(); v2 = stack.Pop(); val = Int64.Parse(v2) - Int64.Parse(v1); stack.Push(val.ToString()); break; case "*": v1 = stack.Pop(); v2 = stack.Pop(); val = Int64.Parse(v2) * Int64.Parse(v1); stack.Push(val.ToString()); break; case "/": v1 = stack.Pop(); v2 = stack.Pop(); val = Int64.Parse(v2) / Int64.Parse(v1); stack.Push(val.ToString()); break; default: stack.Push(token); break; } } return Int32.Parse(stack.Pop()); } }
Nice article admin thanks for share your atricle keep share your knowledge i am waiting for your new post check mens winter jackets polo shirts kindly review and reply me
ReplyDeletesweet, although most stack manipulations can be reused:
ReplyDeletefrom operator import add, sub, mul, truediv
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
ops = {"+": add, "-": sub, "*": mul, "/": truediv}
for token in tokens:
if token in ops:
y, x = stack.pop(), stack.pop()
stack.append(int(ops[token](x, y)))
else:
stack.append(int(token))
return stack[0]
KissAsian is Asian Dramas Platform where you can find all Korean, Chinese, Japanese dramas.
ReplyDeleteGogoanime | Watch gogo anime online, English anime online HD
Watch OnlineNewMovies Online Bollywood Movies Latest Hollywood Movies Online Hindi Movies Dubbed Movies Tamil Movies Download Latest new Movie
championship belts
ReplyDeleteAmazing article written, Get to now about:- tutors in orange county
ReplyDelete