227. Basic Calculator

1. 问题描述

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Tags:String

Similar Problems:(H)Basic Calculator、(H)Expression Add Operators

Solution:

class Solution {
public:
    int calculate(string s) {

    }
};

2. 解答思路

2.1 合法性判断

空字符串
在第一个数字字符('0'~'9')出现前(假设在位置i)，则位置0到位置i的字符只能为空格‘ ’或一个正负号‘+’或‘-’号
除数字、加、减、乘、除、空格字符外，其他字符均为非法字符，返回0。同时，需设置全局标志位，与计算结果为0进行区分
有没有可能多个运算符字符相邻？e.g. "- + /"、“*/-” etc. 不会，因为题目中说You may assume that the given expression is always valid.
若有溢出如何处理

2.2 整数提取

如何从相邻的多个空格与数字字符的串中，提取出整数

2.3 算法

原则：两次循环，先算乘除、再算加减
第1轮循环：若遇到乘除运算符，则将栈顶元素与提取的数字进行运算，删除栈顶元素，将结果入栈，依次类推...
第2轮循环：将栈中元素依次取出进行加法运算

3. 代码

 1 #include <cctype>    //使用isdigit()、isspace()函数时需要
 2 #include <stack>     //使用STL stack时需要
 3 using namespace std;
 4 class Solution {
 5 public:
 6     int calculate(string s) {
 7         long long num = 0;
 8         char ch_Oper = '+';//用于保存提取到的运算符
 9         for (size_t i = 0; i < s.size(); i++)//使用size()函数与使用length()函数的区别
10         {
11             if (isdigit(s[i])) //检查参数c是否为阿拉伯数字0到9
12             {
13                 num = num * 10 + s[i] - '0';
14             }            
15 
16             if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1)//i == s.size()-1表示单独处理最后一个整数
17             {
18                 switch (ch_Oper)
19                 {
20                 case '+':
21                     break;
22                 case '-':
23                     num = -num;
24                     break;
25                 case '*':
26                     num = numStack.top() * num;
27                     numStack.pop();
28                     break;
29                 case '/':
30                     num = numStack.top() / num;
31                     numStack.pop();
32                     break;
33                 default:
34                     break;
35                 }
36 
37                 numStack.push(num);
38                 num  = 0;
39                 ch_Oper = s[i];
40             }         
41         }
42 
43         while (!numStack.empty())
44         {
45             num += numStack.top();
46             numStack.pop();
47         }
48 
49         return (int)num;
50     }
51 
52 private:
53     stack<long long> numStack;
54 };

4. 反思

本题代码中有处处理很是巧妙：

若遇到负号运算符'-'，则令num = -num，从而在第二次循环(while循环)中，只需进行加法运算。

小知识点：

isdigit()、isspace()的用法（需包含#include <ctype.h>(旧版),#include <cctype>(新版)头文件）
STL中stack容器的用法
string s, 如何判断其大小：s.size()、s.length()；如何访问其中的某个字符：s[i]、s.at(i)
如何使用堆栈实现算术运算，如何将减法转换为加法，如何处理乘除运算