4가지 산술 연산에 대한 심층 분석

문자열의 산술 표현식을 어떻게 계산하나요?

정규식을 사용하여 일치시킨다면 좀 말도 안 되는 일이고 일반적인 생각은 재귀를 설계하는 것이지만 Python에서는 재귀 깊이(보통 1000 스택 프레임)에 제한이 있을 뿐만 아니라 꼬리 재귀 최적화를 지원하지 않기 때문에

재귀를 사용하는 것은 적극 권장하지 않습니다.

가장 간단한 방법은 먼저 표현식을 접두사 표현식으로 변환한 후 접두사 표현식을 통해 결과를 계산하는 것입니다.

접두사 표현( 연산자 앞의 )을 폴란드식 표현이라고도 하고, 해당 후위 표현(연산자 뒤의)을 역폴란드 표현이라고도 하며, 우리 생활에서는 ,

가장 일반적인 프로그래밍 언어 ​​에서는 중위 표현을 사용합니다.

중위 표현식을 접두사 표현식으로 변환하는 규칙:

　(1) 두 개의 스택을 초기화합니다: 중간 결과를 저장하는 연산자 스택 S1과 스택 S2

　( 2) 스캔; 중위 표현식은 오른쪽에서 왼쪽으로

(3) 피연산자를 만나면 S2에 push

(4) 연산자를 만나면 S1과 비교 의 우선순위 스택 상단의 연산자 :

　(4-1) S1이 비어 있거나 스택 상단의 연산자가 오른쪽 대괄호 ")"인 경우 이 연산자를 S1에 직접 푸시합니다. stack

　(4-2) 그렇지 않고 우선순위가 스택 맨 위의 연산자보다 높거나 같으면 해당 연산자를 S1에 push

　(4-3) 그렇지 않으면 push S1 스택 최상위 연산자가 팝되어 S2로 푸시됩니다.

다시 (4-1)로 이동하여 S1의 새로운 스택 최상위 연산자

와 비교합니다. (5) 괄호를 만날 때 ：

　 (5-1) 오른쪽 괄호 ")"일 경우 S1을 직접 밀어

(5-2) 왼쪽 괄호 "("일 경우 상단 팝업 시퀀스 연산자에서 S1 스택을 실행하고 오른쪽 괄호가 나올 때까지 S2를 누릅니다.

이때 이 괄호 쌍을 버립니다

(6) 때까지 (2)~(5) 단계를 반복합니다. 표현식의 가장 왼쪽

(7) S1에 남아있는 연산자를 하나씩 Pop하여 S2에 push합니다

(8) S2의 요소를 하나씩 Pop하여 출력하고, 그리고 결과는 중위입니다 접두사 표현식을 사용하여 계산할 때 가장 큰 특징은

중위 표현식을 접두사 표현식

def mid_to_prev(expressions: str):
    priority = {  # 运算符的优先级
        "/": 1,
        "//": 1,
        "*": 1,
        "%": 1,
        "+": 0,
        "-": 0,
        "**": 2 }
    expression_list = expressions.split() # 
    number_stack = [] # 数字栈
    symbol_stack = [] # 运算符栈
    for x in expression_list[::-1]:
        if x.isdigit():             
            number_stack.insert(0, x)  # 如果是整数直接存进去
        else:
            if x == '(':         # 如果是 ( 弹出运算符栈中的运算符直到遇到 ( 
                pop_symbol = symbol_stack[0]
                while pop_symbol != ')':
                    pop_symbol = symbol_stack.pop(0)
                    number_stack.insert(0, pop_symbol)
                    pop_symbol = symbol_stack[0]
                else:
                    symbol_stack.pop(0)
            elif len(symbol_stack) == 0 or symbol_stack[0] == ')' or x == ')' or priority[x] >= priority[symbol_stack[0]]:
                symbol_stack.insert(0, x)  # 当符号栈为空 或者 遇到 ) 或者栈顶的符号是 ) 或者优先级大于等于符号栈顶的运算符优先级 直接存进去

            elif priority[x] < priority[symbol_stack[0]]:  # 优先级小于符号栈顶元素的时候
                while symbol_stack[0] != &#39;)&#39; and priority[x] < priority[symbol_stack[0]]:
                    number_stack.insert(0, symbol_stack.pop(0))
                else:
                    symbol_stack.insert(0, x)
    else:
        while len(symbol_stack) != 0:
            number_stack.insert(0, symbol_stack.pop(0))
    return number_stack

예:

<🎜로 변환한다는 것입니다. >

변환된 접두사 표현식 스택을 조작하는 방법은 간단합니다

(1) 새 목록을 초기화합니다

(2) 숫자를 만나면 오른쪽에서 왼쪽으로 접두사 표현식 목록을 순회합니다. , 새 목록에 저장

(3) 연산자를 만나면 새 목록의 처음 두 숫자를 팝업하고 작업을 수행한 다음 결과를 새 목록에 저장합니다

( 4) 새 목록에서 접두사 표현식 목록을 순회할 때까지 이때 새 목록에는 단 하나의 요소만 있으며, 이것이 최종 결과

def calc(number1,number2,calc): # 两个数运算
    if calc == '/':
        return number1 / number2
    elif calc == '*':
        return number1 * number2
    elif calc == '//':
        return number1 // number2
    elif calc == '**':
        return number1 ** number2
    elif calc == '%':
        return number1 % number2
    elif calc == '+':
        return number1 + number2
    elif calc == '-':
        return number1 - number2

가 됩니다. 전체 결과:

def operation(stack_list:list):
    number = []
    for x in stack_list[::-1]:
        if x.isdigit():
            number.insert(0, x)
        else:
            first = number.pop(0)
            second = number.pop(0)
            tmp = calc(int(first),int(second), x)
            number.insert(0,tmp)
    return number.pop(0)

예:

이전 접두사 표현 결과:

확인된 결과가 맞습니다.

참고 : 표현식은 공백으로 구분해야 합니다

정수만 일치합니다

.

위 내용은 4가지 산술 연산에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!