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 le
17                  :end   ri)
18  (cond
19   ((< 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))))))))
25
26
27(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                           (cond
35                            ((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)))
58
59

posted on 2012-02-19 10:34 coreBugZJ 閱讀(347) 評論(0)  編輯 收藏 引用 所屬分類: ACM 、Algorithm 、Lisp