Leetcode 227 basic caculator
发布日期:2021-09-01 17:00:14 浏览次数:1 分类:技术文章

本文共 3479 字,大约阅读时间需要 11 分钟。

hot3.png

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. 如果后续的是高优先级的操作符,则要先计算后续的操作符;

处理好这两种情况,就可以完成了;

public class Solution {    public static void main(String[] args) {        System.out.println("3+2*2 = " + calculate("3+2*2"));        System.out.println(" 3/2  = " + calculate(" 3/2 "));        System.out.println(" 3+5 / 2  = " + calculate(" 3+5 / 2 "));    }    public static int calculate(String s) {        char[] cs = s.toCharArray();        Stack stack = new Stack();        for (int i = 0; i < cs.length; ) {            if (cs[i] == ' ') {                i++;                continue;            }            if (isMul(cs[i]) || isAdd(cs[i])) {                stack.addOp(cs[i]);                i++;                continue;            }            int num = 0;            while (i < cs.length && isNum(cs[i])) {                num = num * 10 + (cs[i] - '0');                i++;            }            stack.addNum(num);        }        return stack.eval();    }    static boolean isNum(char c) {        return c >= '0' && c <= '9';    }    static boolean isMul(char c) {        return c == '*' || c == '/';    }    static boolean isAdd(char c) {        return c == '+' || c == '-';    }    static class Stack {        int[] nums = new int[3];        int pnum = -1;        char[] ops = new char[2];        int pop = -1;        public void addOp(char op) {            if (isAdd(op) && pop == 0) {                int b = nums[pnum--];                int a = nums[pnum--];                int c = calc(a, b, ops[pop--]);                nums[++pnum] = c;            }            ops[++pop] = op;        }        public void addNum(int num) {            nums[++pnum] = num;            if (pop >= 0 && isMul(ops[pop])) {                int b = nums[pnum--];                int a = nums[pnum--];                int c = calc(a, b, ops[pop--]);                nums[++pnum] = c;            }        }        int calc(int a, int b, char op) {            int c = 0;            switch (op) {                case '+':                    c = a + b;                    break;                case '-':                    c = a - b;                    break;                case '*':                    c = a * b;                    break;                case '/':                    c = a / b;                    break;                default:                    throw new IllegalArgumentException("unknown operator " + c);            }            return c;        }        public int eval() {            if (pnum == 0) {                return nums[pnum--];            } else {                int b = nums[pnum--];                int a = nums[pnum--];                char c = ops[pop--];                return calc(a, b, c);            }        }    }}

这里模拟了一个Stack,

  1. 以处理1 + 2 * 3为例,在加入2的时候,不能计算1 + 2, 因为不知道后续操作符的优先级;等加入*的时候,可以确定当前的优先级肯定比前面的大,(在stack里面至多存在一个*或者/);当加入3的时候,发现前面是一个高优先级的*,可以直接计算,得到6,并把结果放到栈顶。继续处理后续的输入;

  2. 以处理1 + 2 - 3为例,在输入-号之前,和前面的处理是一样的;判断是低优先级的,并且栈底有输入,将栈底的先计算出来,得到3,重新压入栈底(不要忘记了),然后加入新的-;然后加入3;

所以,可以看到,栈里面最多只有4个元素,2个操作数,和2个操作符;

时间复杂度是O(n), 空间复杂度是O(1);

转载于:https://my.oschina.net/u/922297/blog/469449

转载地址:https://blog.csdn.net/weixin_34122810/article/details/92024385 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:SIP开发环境的搭建(转)
下一篇:Different between "git add --all" and "git add ."

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月05日 02时01分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答 2019-04-21
mysql pxc mysql5.7_mysql之PXC5.7.18集群系列——1. Percona XtraDB Cluster 搭建 2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21
java cache 有效期_springboot cache 自定义过期时间及自定义缓存key前缀 2019-04-21
java实验一目的_Java实验报告(实验一) 2019-04-21
java+native+字段_+Java中的native关键字浅析(Java+Native+Interface)++ 2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽 2019-04-21
php sqlsrv 类,php5.*通过sqlsrv建立与mssql的连接 2019-04-21