문자열 형식의 수학 식 평가

Question

이것은 표준 인터뷰 질문으로, 문자열 형태로 주어진 수학 식을 평가합니다. 그래서 제공

, '3+3-6*2' 대답은

-6 지금 표현은 +,-,*,/ 그런 다음 스택을 사용하여 할 수있는 간단한 방법이 네 가지 작업을 지원하는 경우이어야한다.

필자는 삽입 기호 표기법을 후위 문자로 변환 한 다음 스택을 사용하여 해결했지만이 네 가지 연산 만 지원하는 다른 방법을 찾고 있습니다. 이것은이 재귀 어휘 분석기를 설계함으로써 해결 될 수 있지만,이 질문의 범위를 벗어 있다는

def evaluate(self, s: str) -> int: 
    expr = [i for i in re.split(r'(\d+|\W+)', s) if i] 
    rpn = self.convertToPostfix(expr) 
    return self.evalPostfix(rpn) 

def convertToPostfix(self, infix: list) -> list: 
    stack = collections.deque() 
    result = [] 
    for item in infix: 
     if item.isdigit(): 
      result.append(item) 
     else: 
      while len(stack) > 0 and self.has_higher_precedence(stack[-1], item): 
       result.append(stack[-1]) 
       stack.pop() 
      stack.append(item) 
    while len(stack) > 0: 
     result.append(stack.pop()) 
    return result 

def has_higher_precedence(self, a: str, b: str) -> bool: 
    if a == '/' and b == '*' or b == '+' or b == '-': 
     return True 
    if a == '*' and b == '+' or '-': 
     return True 
    if a == '+' and b == '-': 
     return True 
    return False 

def evalPostfix(self, p: list) -> int: 
    stack = collections.deque() 
    for item in p: 
     if item.isdigit(): 
      stack.append(int(item)) 
     elif item[1:].isdigit(): 
      stack.append(int(item)) 
     else: 
      curr = stack.pop() 
      prev = stack.pop() 
      if item == '+': 
       total = prev + curr 
      elif item == '-': 
       total = prev - curr 
      elif item == '*': 
       total = prev * curr 
      else: 
       total = prev/curr 
      stack.append(total) 
    return stack.pop() 

이 또한 내가 알고 있어요, 내 솔루션입니다.

그래서 제 질문은 그런 다음 문자 목록으로 문자열을 저장할 수

Answer 1

Shunting-yard 알고리즘을 수정하여 한 번에 구문 분석하고 평가할 수 있습니다. 후위로 변환의 중간 단계가 필요 없습니다. 괄호가없는 네 개의 표준 수학 연산자만으로 문제를 제한해도 기본 접근 방식은 바뀌지 않습니다.

다음은 링크 된 기사의 표준 Shunting-yard 알고리즘입니다. 아래의 참조를 위해 줄 번호를 추가했습니다.

1: while there are tokens to be read: 
2: read a token. 
3: if the token is a number, then push it to the output queue. 
4: if the token is an operator, then: 
5:  while (there is an operator at the top of the operator stack with 
6:   greater precedence) or (the operator at the top of the operator stack has 
7:      equal precedence and 
8:      the operator is left associative) and 
9:      (the operator at the top of the stack is not a left bracket): 
10:    pop operators from the operator stack, onto the output queue. 
11:  push the read operator onto the operator stack. 
12: if the token is a left bracket (i.e. "("), then: 
13:  push it onto the operator stack. 
14: if the token is a right bracket (i.e. ")"), then: 
15:  while the operator at the top of the operator stack is not a left bracket: 
16:   pop operators from the operator stack onto the output queue. 
17:  pop the left bracket from the stack. 
     /* if the stack runs out without finding a left bracket, then there are 
18:  mismatched parentheses. */ 
19: if there are no more tokens to read: 
20:  while there are still operator tokens on the stack: 
21:   /* if the operator token on the top of the stack is a bracket, then 
22:   there are mismatched parentheses. */ 
23:   pop the operator onto the output queue. 
24: exit. 

수정 사항에는 출력 대기열을 피연산자 스택 : 정수 스택으로 바꾸는 작업이 포함됩니다. 예를 들어 출력 대기열에 번호를 푸는 대신 3 행에서 숫자를 피연산자 스택으로 푸시합니다. 물론 문자를 정수로 변환해야합니다.

다음, 당신은 대신, 라인 10에 당신은 운영자 스택에서 연산자를 나타 어디에서 출력 큐에 밀어 :

1. 는 두 개의 피연산자 피연산자 스택에서 운영자
2. 팝 팝
3. 수행 사용자는 라인 16과 23를 교체

동작 은 오퍼랜드 스택 상에 다시 그 결과를 밀어

같은 종류의 논리.

언제든지 평가할 때 피연산자 스택에 피연산자가 충분하지 않으면 연산자가 일치하지 않습니다 : 2 + 3 + - (단항 + 및 단항 -을 지원하지 않기로 결정한 경우), 또는 2 */3이다.

라인 24에 도달하면 연산자 스택이 비어 있고 피연산자 스택에 단일 값, 즉 최종 결과가 있어야합니다. 피연산자 스택에 둘 이상의 항목이있는 경우 피연산자가 너무 많습니다 (발생하지 않아야 함).

따라서 24 번째 줄을 피연산자 스택의 팝으로 바꾸면 그 결과를 반환 할 수 있습니다.

Shunting-yard는 실제로 언급 한 "재귀 적 어휘 분석기"의 매우 단순화 된 버전입니다. 그러나 재귀를 통해 스택 프레임을 작성하는 대신 스택을 직접 조작합니다.

이렇게하려면 코드를 수정하는 것이 너무 어렵지 않아야합니다. 아래는 evaluateInfix이라고하는 convertToPostfix 함수의 수정 된 버전입니다.이 함수는 모두 한 번에 처리합니다. 작업을 수행의 evaluate 함수는 연산자와 두 개의 피연산자를

def evaluateInfix(self, infix: list) -> int: 
    operatorStack = collections.deque() 
    operandStack = collections.deque() 
    result = [] 
    for item in infix: 
     if item.isdigit(): 
      val = convertDigitToNumber(item) // however that's done 
      // push to operand stack 
      operandStack.append(val) 
     else: 
      while len(operatorStack) > 0 and self.has_higher_precedence(operatorStack[-1], item): 
       // pop two operands from stack, evaluate, and push result 
       // call this "pop and eval" 
       op2 = operandStack[-1] 
       operandStack.pop() 
       op1 = operandStack[-1] 
       operandStack.pop() 
       operator = operatorStack[-1] 
       operatorStack.pop() 
       val = evaluate(operator, op1, op2) // this function evaluates op1 <operator> op2 

       // push result back onto operand stack 
       operandStack.append(val) 
      operatorStack.append(item) 
    while len(operatorStack) > 0: 
     // insert "pop and eval" code here 
    // at this point there should be a single value on the operand stack 
    return operandStack[-1] 

: 나는 파이썬 프로그래머가 아니에요 참고, 그래서 코드가 완벽하게 작동하도록 보장 할 것이다, 그러나 당신에게 아이디어를 줄 것이다 , 결과를 반환합니다. 따라서 ('+', 3, 5)이 주어지면 3+5을 계산하고 8을 반환합니다.

당신이 평가할 때마다, 당신은 2 개의 피연산자와 하나의 연산자를 취하고 있습니다.

테스트 케이스 : 3+5*2.

 operand operator 
char stack  stack 
-------------------------- 
    3  [3]  [] 
    +  [3]  [+] 
    5  [3,5]  [+] 
    *  [3,5]  [+,*] 
    2  [3,5,2] [+,*] 
<end> 
at this point, we're at the end of the string. 
Pop 2 and 5 from the operand stack, pop * from the operator stack, 
and evaluate 
     [3,10] [+] 
pop and eval again 
     [13]  [] 
operator stack is empty. Pop result from operand stack and return. 

Answer 2

네 개의 사업자가있는 경우 스택을 사용하여 O (n)이 시간에이 작업을 수행 할 수있는 간단한 방법이있다 직선적으로 2 회 반복하여 곱셈/나눗셈을 먼저 계산 한 다음 더하기/빼기를 ​​수행합니다. 기호 - 첫 번째 반복에서

즉

는

1+10/2 -> 1 + 5 

다음,

1 + 5 -> 6 

이것은 쉽게 스택으로 구현 될 수있는 당신은 + 또는으로 번호를 추가 할 수 있습니다. 스택에 추가 할 때 / 또는 * 부호에 도달했다면 이전 요소를 팝하고 현재 요소를 곱하거나 나눕니다. 마지막으로 스택에있는 모든 요소의 합계를 찾습니다.

위의 예에서 사용 된 스택의 유일한 요소는 대답 바로 앞에있는 것임을 알 수 있습니다. 이는 합계를 유지하면서 이전 요소를 저장할 수 있고 * 또는 / 부호에 도달하면 합계에서 이전 요소를 빼고 업데이트 된 요소를 추가 할 수 있음을 나타냅니다. 이 방법은 O (1) 추가 저장 장치로 한 번의 O (n) 스캔에서 문제를 효과적으로 해결하므로이 문제에 대한 최적의 솔루션이 될 수 있습니다.

Answer 3

완성을 위해 @Jim Mischel 솔루션을 Python 3 코드 작업으로 게시하십시오.

import re 


class Solution: 
    def evalExpression(self, s): 
     operator_stack, operand_stack = [], [] 
     tokens = [i for i in re.split(r'(\d+|\W+)', s) if i] 
     for token in tokens: 
      if token.isdigit(): 
       operand_stack.append(int(token)) 
      else: 
       while len(operator_stack) > 0 and self.has_higher_precedence(operator_stack[-1], token): 
        val = self.evaluate(operand_stack.pop(), operator_stack.pop(), operand_stack.pop()) 
        operand_stack.append(val) 
       operator_stack.append(token) 
     while len(operator_stack) > 0: 
      val = self.evaluate(operand_stack.pop(), operator_stack.pop(), operand_stack.pop()) 
      operand_stack.append(val) 
     return operand_stack[-1] 

    def has_higher_precedence(self, opr1, opr2): 
     if opr1 == '/' or opr1 == '*' and opr2 == '+' or opr2 == '-': 
      return True 
     return False 

    def evaluate(self, a, b, c): 
     if b == '/': 
      return c/a 
     elif b == '*': 
      return c*a 
     elif b == '-': 
      return c-a 
     else: 
      return c+a 


if __name__ == '__main__': 
    solution = Solution() 
    print(solution.evalExpression('3+3-6*2'))