想吃冰卻又敏感保護不足?工程師靠存股年領百萬股息吉隆坡最便宜行程一覽表不捨學生找「槌」 高中...
2012-12-20 19:12:07 人氣(232) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][樹走訪] 372 - WhatFix Notation

0
收藏
0
推薦

There are three traversal methods commonly used in compilers and calculators:

     prefix
     infix
     postfix

For example, a single expression can be written in each form

     infix:    a + b * c
     prefix:   + a * b c
     postfix:  a b c * +

Note that prefix and postfix ARE NOT mirror images of each other! The advantage of prefix and postfix notations is that parentheses are unnecessary to prevent ambiguity.

In our traversal the following symbols are operators with precedence rules going from highest to lowest:

tabular21


#include <stdio.h>
char infix[105], prefix[105];
int idx;
void dfs(int l, int r) {
    if(l > r)   return;
    char p = prefix[idx], i;
    idx++;
    for(i = l; i <= r; i++)
        if(infix[i] == p)
            break;
    dfs(l, i-1);
    dfs(i+1, r);
    printf(" %c", p);
}
int main() {
    while(gets(infix)) {
        gets(prefix);
        int i, j;
        for(i = 0, j = 0; infix[i]; i++) {
            if(infix[i] != ' ')
                infix[j++] = infix[i];
        }
        infix[j] = '\0';
        for(i = 0, j = 0; prefix[i]; i++) {
            if(prefix[i] != ' ')
                prefix[j++] = prefix[i];
        }
        prefix[j] = '\0';
        printf("INFIX   =>");
        for(i = 0; infix[i]; i++)
            printf(" %c", infix[i]);
        puts("");
        printf("PREFIX  =>");
        for(i = 0; prefix[i]; i++)
            printf(" %c", prefix[i]);
        puts("");
        printf("POSTFIX =>");
        idx = 0;
        dfs(0, j-1);
        puts("");
    }
    return 0;
}

Input

You are given two strings. The first string is the infix version of the expression. The second string is the prefix version of the expression. Determine the postfix version of the expression and print it out on a single line.

All input will be single characters separated by a space.

tabular21

Output

Output must be the same, single characters separated by a space. There are no special sentinels identifying the end of the data.

Sample Input

a + b - c
+ a - b c

Sample Input

INFIX   => a + b - c
PREFIX  => + a - b c
POSTFIX => a b c - +

給中序前序,求後序。

這題不用管他的算數運算元、子,忽略它就可以了。
奇怪的是這題怎麼那麼少人去寫它。

#include <stdio.h>
char infix[105], prefix[105];
int idx;
void dfs(int l, int r) {
if(l > r) return;
char p = prefix[idx], i;
idx++;
for(i = l; i <= r; i++)
if(infix[i] == p)
break;
dfs(l, i-1);
dfs(i+1, r);
printf(" %c", p);
}
int main() {
while(gets(infix)) {
gets(prefix);
int i, j;
for(i = 0, j = 0; infix[i]; i++) {
if(infix[i] != ' ')
infix[j++] = infix[i];
}
infix[j] = '\0';
for(i = 0, j = 0; prefix[i]; i++) {
if(prefix[i] != ' ')
prefix[j++] = prefix[i];
}
prefix[j] = '\0';
printf("INFIX =>");
for(i = 0; infix[i]; i++)
printf(" %c", infix[i]);
puts("");
printf("PREFIX =>");
for(i = 0; prefix[i]; i++)
printf(" %c", prefix[i]);
puts("");
printf("POSTFIX =>");
idx = 0;
dfs(0, j-1);
puts("");
}
return 0;
}

372WhatFix Notation
台長:Morris
人氣(232) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][cycle] 11036 - Eventually Periodic Sequence
此分類上一篇:[UVA][井字遊戲盤面判斷] 10363 - Tic Tac Toe

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文