ホームページ > バックエンド開発 > Python チュートリアル > python实现逆波兰计算表达式实例详解

python实现逆波兰计算表达式实例详解

WBOY
リリース: 2016-06-06 11:15:57
オリジナル
1689 人が閲覧しました

本文实例讲述了python实现逆波兰计算表达式的方法。分享给大家供大家参考。具体分析如下:

逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

# -*- coding: utf-8 -*-

symbol_priority = {}

symbol_priority[0] = ['#']

symbol_priority[1] = ['(']

symbol_priority[2] = ['+', '-']

symbol_priority[3] = ['*', '/']

symbol_priority[4] = [')']

def comparePriority(symbol, RPN_stack, symbol_stack):

  '''Compare priority between two symbols'''

  global symbol_priority

  if len(symbol_stack) > 0:

    symbol_pop = symbol_stack.pop()

  else:

    return

  for list in symbol_priority.values():

    if (symbol in list) and (symbol_pop in list):

      '''same priority'''

      symbol_stack.append(symbol_pop)

      symbol_stack.append(symbol)

      return

    elif symbol in list:

      '''symbol is smaller'''

      RPN_stack.append(symbol_pop)

      #recusion call

      comparePriority(symbol, RPN_stack, symbol_stack)

      return

    elif symbol_pop in list:

      '''symbol is bigger'''

      symbol_stack.append(symbol_pop)

      symbol_stack.append(symbol)

      return

    else:

      continue

    symbol_stack.append(symbol_pop)

    return

def scanEveryone(input_string, RPN_stack, symbol_stack):

  for ch in input_string:

    if ch.isdigit():

      RPN_stack.append(ch)

    else:

      if len(symbol_stack) > 0:

        if ch == '(':

          symbol_stack.append(ch)

        elif ch == ')':

          while True:

            symbol_pop = symbol_stack.pop()

            if symbol_pop == '(':

              break

            else:

              RPN_stack.append(symbol_pop)

        else:

          comparePriority(ch, RPN_stack, symbol_stack)

      else:

        symbol_stack.append(ch)

def scanInput(RPN_stack, symbol_stack):

  input_string = raw_input()

  input_string += '#'

  scanEveryone(input_string, RPN_stack, symbol_stack)

def calRPN(RPN_stack):

  value_stack = []

  RPN_stack.append('#')

  for value in RPN_stack:

    if value == '#':

      return value_stack.pop()

      break

    if value.isdigit():

      value_stack.append(value)

    else:

      right_value = value_stack.pop()

      left_value = value_stack.pop()

      cal_string = left_value + value + right_value

      value_stack.append(str(eval(cal_string)))

def main():

  RPN_stack = []

  symbol_stack = []

  scanInput(RPN_stack, symbol_stack)

  print calRPN(RPN_stack)

if __name__ == '__main__':

  main()

ログイン後にコピー

calRPN.py

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

# -*- coding: utf-8 -*-

symbol_priority = {}

symbol_priority[0] = ['#']

symbol_priority[1] = ['(']

symbol_priority[2] = ['+', '-']

symbol_priority[3] = ['*', '/']

symbol_priority[4] = [')']

def comparePriority(symbol, RPN_stack, symbol_stack):

  '''Compare priority between two symbols'''

  global symbol_priority

  if len(symbol_stack) > 0:

    symbol_pop = symbol_stack.pop()

  else:

    return

  for list in symbol_priority.values():

    if (symbol in list) and (symbol_pop in list):

      '''same priority'''

      symbol_stack.append(symbol_pop)

      symbol_stack.append(symbol)

      return

    elif symbol in list:

      '''symbol is smaller'''

      RPN_stack.append(symbol_pop)

      #recusion call

      comparePriority(symbol, RPN_stack, symbol_stack)

      return

    elif symbol_pop in list:

      '''symbol is bigger'''

      symbol_stack.append(symbol_pop)

      symbol_stack.append(symbol)

      return

    else:

      continue

    symbol_stack.append(symbol_pop)

    return

def scanEveryone(input_string, RPN_stack, symbol_stack):

  for ch in input_string:

    if ch.isdigit():

      RPN_stack.append(ch)

    else:

      if len(symbol_stack) > 0:

        if ch == '(':

          symbol_stack.append(ch)

        elif ch == ')':

          while True:

            symbol_pop = symbol_stack.pop()

            if symbol_pop == '(':

              break

            else:

              RPN_stack.append(symbol_pop)

        else:

          comparePriority(ch, RPN_stack, symbol_stack)

      else:

        symbol_stack.append(ch)

def scanInput(RPN_stack, symbol_stack):

  input_string = raw_input()

  input_string += '#'

  scanEveryone(input_string, RPN_stack, symbol_stack)

def calRPN(RPN_stack):

  value_stack = []

  RPN_stack.append('#')

  for value in RPN_stack:

    if value == '#':

      return value_stack.pop()

      break

    if value.isdigit():

      value_stack.append(value)

    else:

      right_value = value_stack.pop()

      left_value = value_stack.pop()

      cal_string = left_value + value + right_value

      value_stack.append(str(eval(cal_string)))

def main():

  RPN_stack = []

  symbol_stack = []

 

  scanInput(RPN_stack, symbol_stack)

  print calRPN(RPN_stack)

if __name__ == '__main__':

  main()

ログイン後にコピー

希望本文所述对大家的Python程序设计有所帮助。

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート