[EASY][ONP] Transform the Expression - All About Free

Problem

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+^*

Limitation

Time limit: 5s
Source limit: 50000B
Memory limit: 1536MB

Solution

非常简单, 处理一下括号然后按照顺序输出即可.

Golang代码:

package main

import (
    "fmt"
)

var i, j, t, pos int
var experssion string
var expressions []string

func transform_and_print(result string) string {
    if experssion[pos] == '(' {
        pos++
        result = result + transform_and_print("")
        operator := experssion[pos]
        pos++
        result = result + transform_and_print("")
        result = result + string(operator)
        pos++
    } else {
        result = result + string(experssion[pos])
        pos++
    }
    return result
}

func Transform_to_rpn(exp string) string {
    experssion = exp
    pos = 0
    result := ""
    result = transform_and_print(result)
    return result
}

func main() {
    fmt.Scanln(&t)
    expressions = make([]string, t)
    for i = 0; i < t; i++ {
        fmt.Scanf("%s\n", &expressions[i])
    }
    for i = 0; i < t; i++ {
        fmt.Println(Transform_to_rpn(expressions[i]))
    }
}

Submission result

TIME 0.01

MEMORY 771M (这里应该是个BUG, spoj所有golang的内存占用都是771M开始起跳的, 所以应该是小于1M的内存占用)