Basic Calculator - C Solution

1. Introduction

In this post, we delve into creating a basic calculator in C programming. The challenge is to evaluate a string representation of a valid arithmetic expression without using any built-in functions like eval(). This problem is a great exercise in parsing, stack manipulation, and handling arithmetic operations.

Problem

Given a string s representing a valid arithmetic expression, the task is to implement a basic calculator to evaluate it and return the result. The expression can include digits, '+', '-', '(', and ')' characters.

2. Solution Steps

1. Use a stack to handle parentheses and signs.

2. Initialize variables to store the current number and the overall result.

3. Iterate through each character in the string s.

4. Process digits to form numbers.

5. Handle opening parentheses by pushing the current result and sign onto the stack.

6. Handle closing parentheses and '+'/'-' signs.

7. Update the result as you parse through the string.

8. Return the final result.

3. Code Program

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

// Function to calculate the result
int calculate(char* s) {
    int len = strlen(s);
    int* stack = (int*)malloc(len * sizeof(int));
    int top = -1;
    int result = 0;
    int sign = 1;
    int number = 0;

    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c >= '0' && c <= '9') {
            number = 10 * number + (c - '0');
        } else if (c == '+') {
            result += sign * number;
            number = 0;
            sign = 1;
        } else if (c == '-') {
            result += sign * number;
            number = 0;
            sign = -1;
        } else if (c == '(') {
            stack[++top] = result;
            stack[++top] = sign;
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * number;
            number = 0;
            result *= stack[top--]; // sign
            result += stack[top--]; // result
        }
    }

    if (number != 0) {
        result += sign * number;
    }

    free(stack);
    return result;
}

// Main function to test the calculate function
int main() {
    char s[] = "(1+(4+5+2)-3)+(6+8)";
    int result = calculate(s);
    printf("Result: %d\n", result);

    return 0;
}

Output:

Result: 23

Explanation:

1. The calculate function uses a stack to manage parentheses and signs.

2. It iteratively processes each character, forming numbers and applying arithmetic operations.

3. Parentheses are handled by storing the current state on the stack.

4. After processing the entire string, the result is obtained.

5. The main function demonstrates the calculator with an example expression.