# coreBugZJ

## ONP - SPOJ 4. Transform the Expression

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

### Input

```t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
```

Text grouped in [ ] does not appear in the input file.

### Output

```The expressions in RPN form, one per line.
```

### Example

```Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*```
` `
` `
`中缀转后缀，用递归解决。`
`lambda 很好用。`
`LISP SBCL 1(defconstant +max-len+ 420) 2(defconstant +max-pri+ 123456789) 3(defvar *str*) 4(defvar *pri*) 5 6 7(defun solve(le ri) 8 (let ((min-pri +max-pri+) 9       (cur-idx le)10       (min-idx +max-len+))11  (count -1 *pri* :key #'(lambda (x)12                          (when (> min-pri x)13                           (setf min-pri x)14                           (setf min-idx cur-idx))15                          (incf cur-idx))16                  :start le17                  :end   ri)18  (cond19   ((< min-pri +max-pri+)20    (solve le min-idx)21    (solve (1+ min-idx) ri)22    (write-char (elt *str* min-idx)))23   ((= min-pri +max-pri+)24    (write-string (remove #\( (remove #\) (subseq *str* le ri))))))))252627(let ((num (read))28      (tot-pri 0))29 (dotimes (i num)30  (setf *str* (remove #\Space (read-line)))31  (setf *pri* (make-array +max-len+ :fill-pointer 0))32  (setf tot-pri 0)33  (count #\? *str* :key #'(lambda (x)34                           (cond35                            ((alpha-char-p x)36                             (vector-push +max-pri+ *pri*))37                            ((char= x #\+)38                             (vector-push (+ tot-pri 1) *pri*))39                            ((char= x #\-)40                             (vector-push (+ tot-pri 2) *pri*))41                            ((char= x #\*)42                             (vector-push (+ tot-pri 3) *pri*))43                            ((char= x #\/)44                             (vector-push (+ tot-pri 4) *pri*))45                            ((char= x #\^)46                             (vector-push (+ tot-pri 5) *pri*))47                            ((char= x #\()48                             (incf tot-pri 6)49                             (vector-push +max-pri+ *pri*))50                            ((char= x #\))51                             (decf tot-pri 6)52                             (vector-push +max-pri+ *pri*))53                            (t 54                             (vector-push +max-pri+ *pri*)))55                           #\.))56  (solve 0 (length *str*))57  (fresh-line)))5859`
` `

posted on 2012-02-19 10:34 coreBugZJ 阅读(217) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithmLisp