面试题目：(5)基本计算器

题目

• 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
• 示例 1：
  • 输入：s = "1 + 1"
  • 输出：2
• 示例 2：
  • 输入：s = " 2-1 + 2 "
  • 输出：3
• 示例 3：
  • 输入：s = "(1+(4+5+2)-3)+(6+8)"
  • 输出：23
• 注意:
  • 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
  • 1 <= s.length <= 3 * 105
  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
  • s 表示一个有效的表达式
  • '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
  • '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
  • 输入中不存在两个连续的操作符
  • 每个数字和运行的计算将适合于一个有符号的 32位 整数（不单单是个位数）

代码

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

int calculate(char *s) {
    int len = strlen(s);
    int stack[len];
    int top = -1;
    int result = 0;
    int number = 0;
    int sign = 1; 

    for (int i = 0; i < len; i++) {
        char c = s[i];

        if (isdigit(c)) {
            number = number * 10 + (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--];
            result += stack[top--];
        }
    }
    result += sign * number;
    return result;
}

int main() {
    char s[256] = "";
    printf("s = ");
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = '\0';

    int result = calculate(s);
    printf("Result: %d\n", result);

    return 0;
}

代码解析

• 先获取输入的字符串，并去掉后面的换行
• 进行运算处理
  • result：已经计算完的值
  • number：将要计算的值
  • sign：加法为1，减法为-1，默认加法，表示下一个数字将要以什么符号运算
  • 遍历字符串，判断是什么值
    • 是数字，就将其保存在number，如果nember不是0，表示他不是个位数，number就要*10进行升位，再加上当前的值
    • 是加号，将nuber乘以sign再进行加到result中，并将number清0，sign标记为加法
    • 是减号：将nuber乘以sign再进行加到result中，并将number清0，sign标记为减法
    • 是前括号：将已经运算的值保存到栈中，然后再保存当前运算符号到栈中，将result清0，sign恢复默认加法，等于重新开始计算括号里的
    • 是后括号：将nuber乘以sign再进行加到result中，并将number清0，从栈中先取出运算符进行相乘，然后再加上栈中之前已经计算完的值
  • 如果最后是以数字结尾所以还要加上或者减去最后一个数字
  • 返回最后结果