Basic Calculator 基本计算器-Leetcode

1.题目:

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

题目要求是,实现一个基本的计算器,它接受一个字符串作为输入,实现加法减法和小括号。字符串中有0-9,+,-,(,)和空白符号。

可以认为所有的计算数均为非负值。可以认为题目的输入均为有效算式。字符串中可能有空格,你需要自己处理掉。

2.思路:

递归地计算每个子式相加减的值。

何为子式?认为整个算式是第一个子式。第一个被括号括起来的式子是第二个子式。依次类推。

例如,

(1+(4+5+2)-3)+(6+8)

中,第一个子式是(1+(4+5+2)-3)+(6+8)。第二个子式是(1+(4+5+2)-3)。第三个是(4+5+2)。第四个是(6+8)。

那么,

要求第一个子式的值,就等于求第二个子式+第四个子式。

要求第二个子式的值,就等于求1+第三个子式-3。

  • 所以,首先要有一个函数1,它接受一个指针指向某个子式的开头,返回这个子式的值。
  • 其次,要有一个函数2,用于把字符串中的1啊,23啊,84啊之类的字符串转换成相应的数值1,23,84。如果要被转换的字符是'(',说明要转换的内容是一个子式,那么就用函数1处理。

3.代码

给出一份JAVA实现:

public class Solution{
    public int calculate(String s){//这个就是函数1
        int ans=0;
        int sign=1;
        while (location<s.length()){
            ans+=(helper(s)*sign);
            if (location>=s.length()) break;
            if (s.charAt(location)==')') {
                location++;
                return ans;
            }
            sign=(s.charAt(location)=='-')?-1:1;
            location+=1;
        }
        return ans;
    }
    private int location=0;//这个就是给出子式位置的指针
    private int helper(String s){//这个就是函数2
        int op=0;
        while (location<s.length()&&(Character.isDigit(s.charAt(location))||Character.isSpaceChar(s.charAt(location)))){
            if (Character.isDigit(s.charAt(location))){
                op*=10;
                op+=(s.charAt(location)-'0');
            }
            location++;
        }
        if (location<s.length()&&s.charAt(location) == '('){
            location++;
            return calculate(s);
        }
        return op;
    }

}

同时,给出一份C++实现:

class Solution {
private:
    int calculateHelper(string& s, int& location){//函数2
        while (s[location]==' ')
        {
            location++;
        }
        if (s[location]=='(')
        {
            return calculate(s, ++location);
        }
        int ans=0;
        while (s[location]>='0'&& s[location]<='9')
        {
            while (s[location] == ' ')
            {
                location++;
            }
            ans *= 10;
            ans += (s[location] - '0');
            location++;
        }
        return ans;
    }
    int calculate(string& s, int& location){//函数1
        int total = 0;
        int next = 0;
        for (next = location;next<s.length();)
        {
            bool isPlus = (s[next] == '-');//检查是做加法还是减法
            if (s[next]==')')
            {
                return total;
            }
            int temp = calculateHelper(s, location);
            next = location ;
            location = next + 1;
            total = (isPlus)?(total - temp) : (total + temp);

        }
        return total;
    }
public:
    int calculate(string s) {
        int location = 0;//指示位置的指针
        return calculate(s, location);
    }
};

4.另一种思路:

使用栈来完成运算,是常见的算式解法。这里给出一份用两个stack来解题的算法,一个stack用于保存操作数,另一个用于保存操作符。思路就是压入操作数,遇到操作符后把操作数取出来,与字符串中下一个操作数相运算,再压入栈,同时把该操作符出栈丢弃。

class Solution {
private:
    int toInt(string& s, int& location){
        int ans = 0;
        while (location<s.length() && s[location] >= '0'&&s[location] <= '9'){
            ans *= 10;
            ans += (s[location] - '0');
            location++;
        }
        return ans;
    }
    void calculateTwo(stack<char> &op, stack<int> &st)
    {
        char c = op.top();
        op.pop();
        int n1 = st.top();
        st.pop();
        int n2 = st.top();
        st.pop();
        if (!op.empty() && op.top() == '-')
        {
            op.pop();
            op.push('+');
            n2 = -n2;
        }
        n2 = (c == '+') ? (n2 + n1) : (n2 - n1);
        st.push(n2);
    }
public:
    int calculate(string s) {
        stack<int> st;
        stack<char> op;
        bool isNeg = false;
        for (int i = 0; i<s.length();){
            if (s[i] == ' ') {
                i++;
                continue;
            }
            if (s[i] >= '0'&&s[i] <= '9'){
                int j = toInt(s, i);
                st.push(j);
                while (!op.empty()){
                    char c = op.top();
                    if (c == '('){
                        break;
                    }
                    calculateTwo(op, st);
                }
            }
            else if (s[i] == ')'){
                while (!op.empty()){
                    char c = op.top();
                    if (c=='(')
                    {
                        op.pop();
                        break;
                    }
                    calculateTwo(op, st);
                }
                i++;
            }
            else{
                op.push(s[i]);
                i++;
            }
        }
        while (!op.empty())
        {
            calculateTwo(op, st);
        }
        return st.top();
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

15020
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

19440
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13150
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

43230
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17230
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

50620
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

26340
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

11210
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

26530
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励