简单的计算器

题目要求

实现一个简单的计算器，能够计算简单字符串表达式，表达式可以包括小括号，运算符包含+ - * /, 表达式允许有空格,参与运算的数值都是正整数。
示例1

输入: "1 + 2"
输出: 3

示例2

输入:" 2 - 3 + 2 "
输出: 1

示例3

输入:"(1+(4+5+3)-3)+(9+8)"
输出: 27

示例4

输入:"(1+(4+5+3)/4-3)+(6+8)*3"
输出: 43

思路分析

1 表达式预处理

万事开头难，先不考虑如何计算，我们应该先对表达式进行处理，处理以后，只有数值和运算符，这样才能对他们进行具体的操作，比如"1 + 2" 处理后得到['1', '+', '2']， 运算符和数值都分离开了。

这样的解析并不复杂，只需要遍历字符串，解析出数值部分放入到列表中，遇到小括号或者运算符则直接放入列表中，代码如下：

def exp_to_lst(exp):
    lst = []
    start_index = 0    # 数值部分开始位置
    end_index = 0      # 数值部分结束位置
    b_start = False
    for index, item in enumerate(exp):
        # 是数字
        if item.isdigit():
            if not b_start:  # 如果数值部分还没有开始
                start_index = index    # 记录数值部分开始位置
                b_start = True         # 标识数值部分已经开始
        else:
            if b_start:  # 如果数值部分已经开始
                end_index = index     # 标识数值部分结束位置
                b_start = False       # 标识数值部分已经结束
                lst.append(exp[start_index:end_index])   # 提取数值放入列表

            if item in ('+', '-', '*', '/', '(', ')'):    # 运算符直接放入列表
                lst.append(item)

    if b_start:    # 数值部分开始了,但是没有结束,说明字符串最后一位是数字,
        lst.append(exp[start_index:])
    return lst
    
def test_exp_to_lst():
    print exp_to_lst("1 + 2")
    print exp_to_lst(" 2 - 3 + 2 ")
    print exp_to_lst("(1+(4+5+3)-3)+(9+8)")
    print exp_to_lst("(1+(4+5+3)/4-3)+(6+8)*3")

test_exp_to_lst()

程序输出结果为

['1', '+', '2']
['2', '-', '3', '+', '2']
['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '-', '3', ')', '+', '(', '9', '+', '8', ')']
['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '/', '4', '-', '3', ')', '+', '(', '6', '+', '8', ')', '*', '3']

2 中序转后序

1+2 这种表达式是中序表达式，运算符在运算对象的中间，还有一种表达式，运算符在运算对象的后面，称之为后序表达式，也叫逆波兰表达式。1+2 转成后序表达式后是 1 2 +， +号作用于它前面的两个运算对象。

后序表达式相比于中序表达式更容易计算，因此，这一小节，我要把中序表达式转换成后序表达式。

转换时要借助栈这个数据结构，变量postfix_lst 表示后序表达式，遍历中序表达式，根据当前值进行处理：

• 如果遇到数值，则放入到postfix_lst中
• 遇到（ 压如栈中
• 遇到 ），将栈顶元素弹出并放入到postfix_lst中，直到遇到（，最后弹出（
• 遇到运算符，把栈顶元素弹出并放入到postfix_lst中，直到栈顶操作符的运算优先级小于当前运算符，最后将当前运算符压入栈

代码如下：

# 运算优先级
priority_map = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2
}

class Stack(object):
    def __init__(self):
        self.items = []
        self.count = 0

    def push(self, item):
        """
        放入一个新的元素
        :param item:
        :return:
        """
        self.items.append(item)
        self.count += 1

    def top(self):
        # 获得栈顶的元素
        return self.items[self.count-1]

    def size(self):
        # 返回栈的大小
        return self.count

    def pop(self):
        # 从栈顶移除一个元素
        item = self.top()
        del self.items[self.count-1]
        self.count -= 1
        return item
        
def infix_exp_2_postfix_exp(exp):
    """
    中序表达式转后序表达式
    """
    stack = Stack()
    exp_lst = exp_to_lst(exp)
    postfix_lst = []
    for item in exp_lst:
        # 如果是数值,直接放入到postfix_lst 中
        if item.isdigit():
            postfix_lst.append(item)
        elif item == '(':
            # 左括号要压栈
            stack.push(item)
        elif item == ')':
            # 遇到右括号了,整个括号里的运算符都输出到postfix_lst
            while stack.top() != '(':
                postfix_lst.append(stack.pop())
            # 弹出左括号
            stack.pop()
        else:
            # 遇到运算符,把栈顶输出,直到栈顶的运算符优先级小于当前运算符
            while stack.size() != 0 and stack.top() in ("+-*/")\
                    and priority_map[stack.top()] >= priority_map[item]:
                postfix_lst.append(stack.pop())
            # 当前运算符优先级更高,压栈
            stack.push(item)

    # 最后栈里可能还会有运算符
    while stack.size() != 0:
        postfix_lst.append(stack.pop())

    return postfix_lst
    
print infix_exp_2_postfix_exp("1 + 2")
print infix_exp_2_postfix_exp(" 2 - 3 + 2 ")
print infix_exp_2_postfix_exp("(1+(4+5+3)-3)+(9+8)")
print infix_exp_2_postfix_exp("(1+(4+5+3)/4-3)+(6+8)*3")

程序输出结果为

['1', '2', '+']
['2', '3', '-', '2', '+']
['1', '4', '5', '+', '3', '+', '+', '3', '-', '9', '8', '+', '+']
['1', '4', '5', '+', '3', '+', '4', '/', '+', '3', '-', '6', '8', '+', '3', '*', '+']

3 后序表达式计算

后续表达式计算同样需要用到栈，这个算法在逆波兰表达式计算的练习题中已经有讲解，直接复用代码

def cal_exp(expression):
    stack = Stack()
    for item in expression:
        if item in "+-*/":
            # 遇到运算符就从栈里弹出两个元素进行计算
            value_1 = stack.pop()
            value_2 = stack.pop()
            if item == '/':
                res = int(operator.truediv(int(value_2), int(value_1)))
            else:
                res = eval(value_2 + item + value_1)
            # 计算结果最后放回栈,参与下面的计算
            stack.push(str(res))
        else:
            stack.push(item)

    res = stack.pop()
    return res

全部代码

# coding=utf-8
import operator

# 运算优先级
priority_map = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2
}

class Stack(object):
    def __init__(self):
        self.items = []
        self.count = 0

    def push(self, item):
        """
        放入一个新的元素
        :param item:
        :return:
        """
        self.items.append(item)
        self.count += 1

    def top(self):
        # 获得栈顶的元素
        return self.items[self.count-1]

    def size(self):
        # 返回栈的大小
        return self.count

    def pop(self):
        # 从栈顶移除一个元素
        item = self.top()
        del self.items[self.count-1]
        self.count -= 1
        return item


# 表达式中序转后序
def infix_exp_2_postfix_exp(exp):
    """
    中序表达式转后序表达式
    """
    stack = Stack()
    exp_lst = exp_to_lst(exp)
    postfix_lst = []
    for item in exp_lst:
        # 如果是数值,直接放入到postfix_lst 中
        if item.isdigit():
            postfix_lst.append(item)
        elif item == '(':
            # 左括号要压栈
            stack.push(item)
        elif item == ')':
            # 遇到右括号了,整个括号里的运算符都输出到postfix_lst
            while stack.top() != '(':
                postfix_lst.append(stack.pop())
            # 弹出左括号
            stack.pop()
        else:
            # 遇到运算符,把栈顶输出,直到栈顶的运算符优先级小于当前运算符
            while stack.size() != 0 and stack.top() in ("+-*/")\
                    and priority_map[stack.top()] >= priority_map[item]:
                postfix_lst.append(stack.pop())
            # 当前运算符优先级更高,压栈
            stack.push(item)

    # 最后栈里可能还会有运算符
    while stack.size() != 0:
        postfix_lst.append(stack.pop())

    return postfix_lst




def exp_to_lst(exp):
    """
    表达式预处理，转成列表形式
    """
    lst = []
    start_index = 0    # 数值部分开始位置
    end_index = 0      # 数值部分结束位置
    b_start = False
    for index, item in enumerate(exp):
        # 是数字
        if item.isdigit():
            if not b_start:  # 如果数值部分还没有开始
                start_index = index    # 记录数值部分开始位置
                b_start = True         # 标识数值部分已经开始
        else:
            if b_start:  # 如果数值部分已经开始
                end_index = index     # 标识数值部分结束位置
                b_start = False       # 标识数值部分已经结束
                lst.append(exp[start_index:end_index])   # 提取数值放入列表

            if item in ('+', '-', '*', '/', '(', ')'):    # 运算符直接放入列表
                lst.append(item)

    if b_start:    # 数值部分开始了,但是没有结束,说明字符串最后一位是数字,
        lst.append(exp[start_index:])
    return lst


def cal_exp(expression):
    """
    计算后续表达式
    """
    stack = Stack()
    for item in expression:
        if item in "+-*/":
            # 遇到运算符就从栈里弹出两个元素进行计算
            value_1 = stack.pop()
            value_2 = stack.pop()
            if item == '/':
                res = int(operator.truediv(int(value_2), int(value_1)))
            else:
                res = eval(value_2 + item + value_1)
            # 计算结果最后放回栈,参与下面的计算
            stack.push(str(res))
        else:
            stack.push(item)

    res = stack.pop()
    return res


def test_exp_to_lst():
    print exp_to_lst("1 + 2")
    print exp_to_lst(" 2 - 3 + 2 ")
    print exp_to_lst("(1+(4+5+3)-3)+(9+8)")
    print exp_to_lst("(1+(4+5+3)/4-3)+(6+8)*3")


def test_infix_exp_2_postfix_exp():
    print cal_exp(infix_exp_2_postfix_exp("1 + 2"))
    print cal_exp(infix_exp_2_postfix_exp(" 2 - 3 + 2 "))
    print cal_exp(infix_exp_2_postfix_exp("(1+(4+5+3)-3)+(9+8)"))
    print cal_exp(infix_exp_2_postfix_exp("(1+(4+5+3)/4-3)+(6+8)*3"))


if __name__ == '__main__':
    test_infix_exp_2_postfix_exp()