栈实现计算器 中缀表达式转后缀表达式

逻辑

实现计算器只需要一个栈。数值直接进入后缀表达式。运算符是否进入栈取决于其优先级是否大于栈顶运算符的优先级，如果大于则入栈，否则栈顶运算符出栈，重复比较直至其能入栈为止。
计算时，后缀表达式的数值直接入栈。遇到运算符时每次从后缀表达式中取出一到两个数值参与运算，运算结果直接入栈。若后缀表达式扫描完毕后栈中仅存在一个数值，则这个值就是表达式的计算结果。
👉C语言实现计算器代码点此

运行截图

代码

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
表达式转换。
'''
import math
BRACKET_L = '('
BRACKET_R = ')'
MINUS = '-'
SPACE = ' '
TAG_LVL = 'lvl'
TAG_SINGLE = 'single'
TAG_CALL = 'call'


def split(string: str, operators: set, values: set) -> list:
    """分割表达式。

    Parameters
    ----------
    string : str
        表达式
    operators : set
        已知表示运算符的字符串
    values : set
        已知表示值的字符串

    Returns
    -------
    list
        拆分的表达式。
    """
    self_op = [BRACKET_L, BRACKET_R]
    ops = list(operators.difference(set(self_op)))
    ops.sort(key=lambda e: len(e), reverse=True)
    ops = self_op+ops
    r = string+''
    rep = '%s%s%s' % (SPACE, r'%s', SPACE)
    ds = '%s%s' % (SPACE, SPACE)
    s = SPACE
    for e in ops+list(values):
        r = r.replace(e, rep % e)
    while r.find(ds) >= 0:
        r = r.replace(ds, s)
    ret = r.split(s)
    return ret


def to_reverse_polish_notation(string: str, operators: dict, values: set) -> list:
    """将中缀表达式转换为后缀表达式。表达式中不能含有多余的逗号和运算符。

    Parameters
    ----------
    string : str
        中缀表达式字串
    operators : dict
        运算符为键，对应运算符优先级为值的键值对
    values : set
        表示常量的值的字符串的集合

    Returns
    -------
    list
        后缀表达式。
    """
    ops = set(operators.keys())
    raw = split(string, ops, values)
    res = []
    stack = []
    length = len(raw)
    for i in range(length):
        hold = raw[i]
        if hold == BRACKET_L:  # 是左括号
            stack.append(hold)
        elif hold == BRACKET_R:  # 是右括号
            while True:
                if stack == [] or stack[-1] == BRACKET_L:
                    stack.pop()  # 弹出左括号
                    break
                else:  # 弹出左括号之后的所有运算符
                    res.append(stack.pop())
        elif hold not in ops:  # 是值
            res.append(hold)
        else:  # 是运算符
            while True:
                push = stack == []  # push是一个判断条件
                push = push or stack[-1] == BRACKET_L
                if not push:
                    top_lvl = operators[stack[-1]][TAG_LVL]
                    hold_lvl = operators[hold][TAG_LVL]
                    push = top_lvl < hold_lvl
                if push:  # 空栈或当前运算符优先级高于栈顶运算符
                    stack.append(hold)
                    break
                else:  # 弹出运算符
                    res.append(stack.pop())
    while stack != []:
        res.append(stack.pop())
    return res


def calc(rpb: list, operators: dict, values: dict) -> float:
    """计算后缀表达式。

    Parameters
    ----------
    rpb : list
        后缀表达式
    operators : dict
        运算符
    values : dict
        常值

    Returns
    -------
    float
        计算结果。
    """
    res = []
    ops = operators.keys()
    vals = values.keys()
    for e in rpb:
        if e == '':
            pass
        elif e in ops:
            if operators[e][TAG_SINGLE]:  # 是单目运算符
                v = None if res == [] else res.pop()
                res.append(operators[e][TAG_CALL](v))
            else:  # 是双目运算符
                v1 = None if res == [] else res.pop()
                v2 = None if res == [] else res.pop()
                res.append(operators[e][TAG_CALL](v1, v2))
            pass
        elif e in vals:  # 是常量
            res.append(values[e])
        else:  # 尝试解析为数字
            res.append(float(e))
    ret = res.pop()
    if res != []:
        raise Exception()
    return ret


ops = {
   
    '+': {
   
        TAG_LVL: 1,
        TAG_SINGLE: False,
        TAG_CALL: lambda a, b: a if b is None else a+b
    },
    '-': {
   
        TAG_LVL: 1,
        TAG_SINGLE: False,
        TAG_CALL: lambda a, b: -a if b is None else a-b
    },
    '*': {
   TAG_LVL: 2, TAG_SINGLE: False, TAG_CALL: lambda a, b: a*b},
    '/': {
   TAG_LVL: 2, TAG_SINGLE: False, TAG_CALL: lambda a, b: b/a},
    '^': {
   TAG_LVL: 3, TAG_SINGLE: False, TAG_CALL: lambda a, b: b**a},
    'ln': {
   TAG_LVL: 4, TAG_SINGLE: True, TAG_CALL: lambda a: math.log(a)},
    'sin': {
   TAG_LVL: 4, TAG_SINGLE: True, TAG_CALL: lambda a: math.sin(a)},
    'cos': {
   TAG_LVL: 4, TAG_SINGLE: True, TAG_CALL: lambda a: math.cos(a)},
    'tan': {
   TAG_LVL: 4, TAG_SINGLE: True, TAG_CALL: lambda a: math.tan(a)},
    'lg': {
   TAG_LVL: 4, TAG_SINGLE: True, TAG_CALL: lambda a: math.log10(a)}
}
vals = {
   
    'pi': math.pi,
    'e': math.e
}
print('输入表达式：', end='')
string = input()  # '-(sin(pi*3/2))^2'
try:
    rpn = to_reverse_polish_notation(string, ops, set(vals.keys()))
    print('后缀表达式：%s' % rpn)
    print('计算结果：%f' % calc(rpn, ops, vals))
except:
    print('无法解析此公式。')