limour-blog.github.io/source/_posts/2020-12-12-【探索】利用后缀表达式解方程.md

---

title: 【探索】利用后缀表达式解方程 urlname: Solving-equations-using-postfix-notation index_img: https://api.limour.top/randomImg?d=2024-01-19 22:41:03 date: 2020-12-12 06:41:03 tags: 探索

excerpt: 这段Python代码实现了使用后缀表达式解方程的功能。它包括了一个栈类（Stack）和一个多项式类（Polynomial）。通过中缀表达式转后缀表达式的方式处理方程，最终实现了解一元一次方程的功能。代码包含了多个方法，如多项式的加法、减法、乘法、除法等操作。在解方程时，它先进行表达式的简化和转换，然后输出方程的解或者判断方程是否是一元一次方程。

import re
from fractions import Fraction

class Stack(list):
    def isEmpty(self):
        return self == []
    def peek(self):
        if self == []: return None
        else: return self[-1]
    def size(self):
        return len(self)
    push = list.append
    def pop(self):
        if self == []: return None
        else: return super().pop()

class Polynomial(list):
    def __init__(self, value):
        for item in value: self.append(Fraction(item))
    def add(self, value):
        if len(self) < len(value): self += [Fraction(0)]*(len(value)-len(self))
        for i in range(len(value)): self[i] += value[i]
    def sub(self, value):
        if len(self) < len(value): self += [Fraction(0)]*(len(value)-len(self))
        for i in range(len(value)): self[i] -= value[i]
    def mul(self, value):
        tmp = self.copy()
        size = len(self)
        self.clear()
        self += [Fraction(0)]*(size+len(value)-1)
        for i,item in enumerate(value):
            for j in range(size):
                self[i+j] += tmp[j]*item
    def divn(self, n):
        if type(n) is Polynomial:
            for i in range(len(self)): self[i] /= n[0]
        else:
            _n = Fraction(n)
            for i in range(len(self)): self[i] /= _n
    def __str__(self):
        if self == []:
            return '0'
        elif len(self) == 1:
            return str(self[0])
        elif len(self) == 2:
            return f'({self[1]})x + {self[0]}'
        else: pass

def get_Formula(equation):
    return equation.replace(' ','').split('=')

_ep = re.compile(r'([\+\-\*/()][^\+\-\*/()]+)')
_op = {
    '+': lambda x,y:x.add(y),
    '-': lambda x,y:x.sub(y),
    '*': lambda x,y:x.mul(y),
    '/': lambda x,y:x.divn(y)
}
def _middle2behind(Fma, res, s, e):
    sta = Stack()
    _s = s
    while s < e:
        if Fma[s] in '+-':
            if sta.isEmpty():
                sta.push(Fma[s])
                s += 1
            elif sta.peek() in '*/':
                while sta: res.push(sta.pop())
                sta.push(Fma[s])
                s += 1
            elif sta.peek() in '+-':
                res.push(sta.pop())
                sta.push(Fma[s])
                s += 1
        elif Fma[s] in '*/':
            if sta.isEmpty():
                sta.push(Fma[s])
                s += 1
            elif sta.peek() in '+-':
                sta.push(Fma[s])
                s += 1
            elif sta.peek() in '*/':
                res.push(sta.pop())
                sta.push(Fma[s])
                s += 1
        elif Fma[s] == '(':
            s += 1
            d = _middle2behind(Fma, res, s, e)
            s += d
        elif Fma[s] == ')':
            s += 1
            break
        else:
            res.push(Fma[s])
            s += 1
    while sta: res.push(sta.pop())
    return s-_s
def middle2behind(Formula):
    if Formula.startswith('-'): Formula = '0' + Formula
    expr = _ep.findall(Formula.replace('(-','(0-'))
    res = Stack()
    _middle2behind(expr, res, 0, len(expr))
    return res
def str2polynomial(_str):
    if _str.endswith('x'):
        if _str == 'x': return Polynomial((0, 1))
        return Polynomial((0, _str.rstrip('x')))
    else: return Polynomial((_str,))
def not_eval(Formula):
    expr = middle2behind(Formula)
    #print(expr)
    sta = Stack()
    for item in expr:
        if item in _op:
            y = sta.pop()
            x = sta.pop()
            _op[item](x, y)
            sta.push(x)
        else: sta.push(str2polynomial(item))
        #print(sta)
    return sta.pop()

_x = re.compile(r'[a-zA-Z]+')
def solve_eq(equation):
    print(f'equation is \t\t{equation}')
    xname = set(_x.findall(equation))
    if len(xname) != 1: 
        #print(xname)
        print(f'别逗，{equation}是一元一次方程吗?')
        return
    xname = xname.pop()
    Fma = get_Formula(_x.sub('x', equation))
    if len(Fma) != 2:
        print('{equation}不是标准方程！')
        return
    Fma = [not_eval(expr) for expr in Fma]
    print(f'Simplification is \t{Fma[0]} = {Fma[1]}')
    tmp = Fma[0]
    tmp.sub(Fma[1])
    print(f'Transposition is \t{tmp} = 0')
    if len(tmp) < 2 or tmp[1] == 0:
        print(f'{xname} 无解')
    else:
        x = -tmp[0]/tmp[1]
        print(f'{xname} = x = {x}')