时间戳

首页 > 技术文章 > LeetCode#227.Basic Calculator II

LeetCode#227.Basic Calculator II

yatesxu 2016-05-08 19:09 原文

题目

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

大意：一个不包含括号，包含空格的计算器

思路

采用堆栈实现。从头到尾扫描字符串：

  1. 如果是数字，作为当前的各位，之前的数左移一位作为高位。
  2. 如果是符号，若是加减法，将数字乘以符号压入堆栈。
  3. 如果是乘除法，从堆栈弹出一个数，与当前数相乘除压回堆栈。

注意，使用后缀表达式，先读出两个数在读出符号，顺序应为：

  1. 前一个符号的初始值为+（因为读出第一个符号时，对第一个数字的操作一定是压入堆栈，同+的情况）
  2. 读出一个数字，压入堆栈
  3. 读出一个符号
  4. 在读出一个数字
  5. 根据前一个符号决定当前操作
  6. 操作完成后将刚读出的符号记为前一个符号。

这样就相当于完成了普通表达式到后缀表达式的转换。

代码

class Solution {
public:
    int calculate(string s) {
        stack<int> myStack;
        char sign = '+';
        int num = 0,res=0;
        for (int i = 0; i < s.size(); i++){
            if (isdigit(s[i]))
                num = num * 10 + s[i] - '0';
            if (((!isdigit(s[i])) && (!isspace(s[i])))||(i==s.size()-1)){
                if (sign == '+')
                    myStack.push(num);
                if (sign == '-')
                    myStack.push(num*-1);
                if (sign == '*'){
                    num = myStack.top()*num;
                    myStack.pop();
                    myStack.push(num);
                }
                if (sign == '/'){
                    num = myStack.top() / num;
                    myStack.pop();
                    myStack.push(num);
                }
                sign = s[i];
                num = 0;
            }
        }
        while (!myStack.empty()){
            res += myStack.top();
            myStack.pop();
        }
        return res;
    }
};

其他

关于”ctype.h”

image

图片来自维基百科<https://zh.wikipedia.org/wiki/Ctype.h>

推荐阅读