Evaluate Reverse Polish Notation - C Solution

1. Introduction

In this post, we tackle a classic problem in computer science, known as "Evaluate Reverse Polish Notation". This problem involves evaluating an arithmetic expression written in postfix notation, where operators follow their operands. It's an excellent exercise in stack utilization and string manipulation in C.

Problem

Given an array of strings tokens, representing an arithmetic expression in Reverse Polish Notation (RPN), the task is to evaluate the expression and return the resulting integer. The expression includes the operators '+', '-', '*', and '/', and integer operands.

2. Solution Steps

1. Initialize a stack to store integers.

2. Iterate through each token in the array.

3. If a token is a number, push it onto the stack.

4. If a token is an operator, pop the top two elements from the stack, apply the operation, and push the result back onto the stack.

5. After processing all tokens, the top of the stack will contain the final result.

6. Return the result.

3. Code Program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to evaluate the expression
int evalRPN(char** tokens, int tokensSize) {
    int* stack = (int*)malloc(tokensSize * sizeof(int));
    int top = -1, a, b;

    for (int i = 0; i < tokensSize; i++) {
        if (strcmp(tokens[i], "+") == 0) {
            b = stack[top--];
            a = stack[top--];
            stack[++top] = a + b;
        } else if (strcmp(tokens[i], "-") == 0) {
            b = stack[top--];
            a = stack[top--];
            stack[++top] = a - b;
        } else if (strcmp(tokens[i], "*") == 0) {
            b = stack[top--];
            a = stack[top--];
            stack[++top] = a * b;
        } else if (strcmp(tokens[i], "/") == 0) {
            b = stack[top--];
            a = stack[top--];
            stack[++top] = a / b;
        } else {
            stack[++top] = atoi(tokens[i]);
        }
    }

    int result = stack[top];
    free(stack);
    return result;
}

// Main function to test the evalRPN function
int main() {
    char* tokens[] = {"2", "1", "+", "3", "*"};
    int result = evalRPN(tokens, 5);
    printf("Result: %d\n", result);

    return 0;
}

Output:

Result: 9

Explanation:

1. evalRPN processes the tokens using a stack to perform arithmetic operations.

2. Numbers are pushed onto the stack, and operations are performed with the top two numbers.

3. The final result is obtained by popping the top of the stack.

4. The main function demonstrates the evaluation of a simple expression.

5. The implementation covers basic arithmetic operations and integer parsing.