| 115 | |
| 116 | # 利用栈实现普通多项式的后缀表达式 |
| 117 | def infixToPostfix(infixexpr): |
| 118 | prec = {} |
| 119 | prec['*'] = 3 |
| 120 | prec['/'] = 3 |
| 121 | prec['+'] = 2 |
| 122 | prec['-'] = 2 |
| 123 | prec['('] = 1 |
| 124 | opStack = Stack() |
| 125 | postfixList = [] |
| 126 | tokenList = infixexpr.split() |
| 127 | |
| 128 | for token in tokenList: |
| 129 | if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789': |
| 130 | postfixList.append(token) |
| 131 | elif token == '(': |
| 132 | opStack.push(token) |
| 133 | elif token == ')': |
| 134 | topToken = opStack.pop() |
| 135 | while topToken != '(': |
| 136 | postfixList.append(topToken) |
| 137 | topToken = opStack.pop() |
| 138 | else: |
| 139 | while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]): |
| 140 | postfixList.append(opStack.pop()) |
| 141 | opStack.push(token) |
| 142 | |
| 143 | while not opStack.isEmpty(): |
| 144 | postfixList.append(opStack.pop()) |
| 145 | |
| 146 | return ''.join(postfixList) |
| 147 | |
| 148 | # print(infixToPostfix("A * B + C * D")) |
| 149 | # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )")) |