文档章节

Basic CalculatorI II LeetCode OJ

JoshuaShaw
 JoshuaShaw
发布于 2015/09/09 19:56
字数 307
阅读 23
收藏 0
class Solution(object):

    def __init__(self):
        self.expressionList = []

    def priority(self, c):
        if(c=="*" or c=="/"):
            return 2
        elif(c=="+" or c=="-"):
            return 1
        else:
            return 0

    def leftPirorityIsNotLess(self, c1, c2):
        if(c1==None):
            return False
        return self.priority(c1)>=self.priority(c2)

    def isNumber(self, c):
        if("0"<=c and c<="9"):
            return True
        return False

    def isLeftBracket(self, c):
        if(c=="("):
            return True
        return False

    def isRightBracket(self, c):
        if(c==")"):
            return True
        return False

    def isOperator(self, c):
        if(c=="+" or c=="-" or c=="*" or c=="/"):
            return True
        return False

    def parse(self, s):
        stack = Stack()
        numString = ""
        charList = list(s)

        for char in charList:
            if(self.isNumber(char)):
                numString += char

            else:
                if(len(numString)>0):
                    self.expressionList.append(Node().setNum(int(numString)))
                    numString = ""
                
                if(self.isLeftBracket(char)):
                    stack.push(char)

                elif(self.isOperator(char)):
                    while(self.leftPirorityIsNotLess(stack.top(), char)):
                        self.expressionList.append( Node().setOp(stack.pop()))
                    stack.push(char)

                elif(self.isRightBracket(char)):
                    while(not self.isLeftBracket(stack.top())):
                        self.expressionList.append(Node().setOp(stack.pop()))
                    stack.pop()
                #default

        if(len(numString)>0):
            self.expressionList.append(Node().setNum(int(numString)))
            numString = ""

        while(not stack.isEmpty()):
            self.expressionList.append(Node().setOp(stack.pop()))

    def calculate(self, s):
        self.parse(s);

        stack = Stack()
        for node in self.expressionList:
            if(node.isNumber()):
                stack.push(node.num)
            else:
                r = stack.pop();
                l = stack.pop();
                stack.push(node.make(l,r));

        return stack.pop();
        
class Node(object):
    def __init__(self):
        self.flag = False;
    def setNum(self, num):
        self.num = num
        self.flag = True;
        return self
    def setOp(self, op):
        self.op = op
        return self
    def isNumber(self):
        return self.flag
    def make(self, left, right):
        if(self.op=="+"):
            return left + right
        if(self.op=="-"):
            return left - right
        if(self.op=="*"):
            return left * right
        if(self.op=="/"):
            return left / right
            
class Stack(object):
    def __init__(self):
        self.items = []
    def push(self, x):
        self.items.append(x)
    def pop(self):
        return self.items.pop()
    def top(self):
        if not self.isEmpty():
            return self.items[len(self.items)-1]
    def isEmpty(self):
        if(len(self.items)==0):
            return True
        else:
            return False


© 著作权归作者所有

JoshuaShaw
粉丝 5
博文 27
码字总数 15604
作品 0
湛江
程序员
私信 提问
[LeetCode] Read N Characters Given Read4 II - Call multiple times 用Read4来读取N个字符之二 - 多次调用

The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 ch......

机器的心脏
2017/12/15
0
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
94
0
[LeetCode] Shortest Palindrome 最短回文串

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this tran......

机器的心脏
2017/12/02
0
0
Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", whic......

jdflyfly
2014/06/24
1K
0
[oj.leetcode] 跟leecode的博客旧文说再见

在我目前的博客中,数量最多的就是leecode问题的解答。这些归在leetcode标签之下的文章,其中的绝大部分,基本就是简单一说思路,然后贴代码。 比如这种 它们的共同特征就是结构较简单,讲解...

teaspring
2015/04/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JWT学习总结

官方 https://jwt.io 英文原版 https://www.ietf.org/rfc/rfc7519.txt 或 https://tools.ietf.org/html/rfc7519 中文翻译 https://www.jianshu.com/p/10f5161dd9df 1. 概述 JSON Web Token(......

冷基
54分钟前
3
0
AOP的学习(1)

AOP 理解AOP编程思想(面向方法、面向切面) spring AOP的概念 方面 -- 功能 目标 -- 原有方法 通知 -- 对原有方法增强的方法 连接点 -- 可以用来连接通知的地方(方法) 切入点 -- 将用来插入...

太猪-YJ
今天
4
0
一张图看懂亮度、明度、光度、光亮度、明亮度

亮度、明度、光亮度,Luminance和Brightness、lightness其实都是一个意思,只是起名字太难了。 提出一个颜色模型后,由于明度的取值与别人的不同,为了表示区别所以就另想一个词而已。 因此在...

linsk1998
昨天
8
0
Python应用:python链表示例

前言 python链表应用源码示例,需要用到python os模块方法、函数和类的应用。 首先,先简单的来了解下什么是链表?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是...

python小白1
昨天
4
0
Source Insight加载源码

Source Insight是一个图形化的源代码查看工具(当然也可以作为编译工具)。如果一个项目的源代码较多,此工具可以很方便地查找到源代码自建的依赖关系。 1.创建工程 下图为Snort源代码的文件...

天王盖地虎626
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部