Sponsored
Sponsored
The stack-based approach is ideal for evaluating Reverse Polish Notation (RPN) expressions because it naturally follows the Last-In-First-Out (LIFO) principle, which aligns with the evaluation order of RPN expressions. The key idea is to iterate through the tokens, pushing operands onto the stack, and handling operators by popping the required number of operands from the stack, performing the operation, and pushing the result back onto the stack.
Time Complexity: O(n), where n is the number of tokens.
Space Complexity: O(n) due to stack usage.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int evalRPN(char **tokens, int tokensSize) {
6 int stack[tokensSize];
7 int top = -1;
8 for (int i = 0; i < tokensSize; i++) {
9 char *token = tokens[i];
10 if (!strcmp(token, "+") || !strcmp(token, "-") || !strcmp(token, "*") || !strcmp(token, "/")) {
11 int b = stack[top--];
12 int a = stack[top--];
13 int result;
14 if (strcmp(token, "+") == 0) result = a + b;
15 else if (strcmp(token, "-") == 0) result = a - b;
16 else if (strcmp(token, "*") == 0) result = a * b;
17 else result = a / b;
18 stack[++top] = result;
19 } else {
20 stack[++top] = atoi(token);
21 }
22 }
23 return stack[top];
24}
25The program uses an integer array as a stack to evaluate the RPN expression. As it processes each token:
The final result is the only element left on the stack.