URI Online Judge | 1077
Infixa para Posfixa
Por Neilor Tonin, URI 
Brasil
Timelimit: 1 Brasil
O Professor solicitou que você escreva um programa que converta uma expressão na forma infixa (como usualmente conhecemos) para uma expressão na forma posfixa. Como você sabe, os termos in (no meio) e pos (depois) se referem à posição dos operadores. O programa terá que lidar somente com operadores binários +,-,*,/,^, parênteses, letras e números. Um exemplo seria uma expressão como:
(A*B+2*C^3)/2*A. O programa deve converter esta expressão (infixa) para a expressão posfixa: AB*2C3^*+2/A*
(A*B+2*C^3)/2*A. O programa deve converter esta expressão (infixa) para a expressão posfixa: AB*2C3^*+2/A*
Entrada
A primeira linha da entrada contém um valor inteiro N (N < 1000), que indica o número de casos de teste. Cada caso de teste a seguir é uma expressão válida na forma infixa, com até 300 caracteres.
Saída
Para cada caso, apresente a expressão convertida para a forma posfixa
Infix to Posfix
By Neilor Tonin, URI Brazil
Timelimit: 1 Brazil
The teacher asked you to write a program that convert an infix expression to a postfix expression. Like you know, the terms in and pos are according with the operators position. The program will have to handle only with the binary operators +, -, *, /, ^. parenthesis, letters and numbers. An example would be an expression like:
(A*B+2*C^3)/2*A. The program must convert this expression (infix) to the posfix expression: AB*2C3^*+2/A*
All expressions of the test cases are expressions with valid sintax.
(A*B+2*C^3)/2*A. The program must convert this expression (infix) to the posfix expression: AB*2C3^*+2/A*
All expressions of the test cases are expressions with valid sintax.
Input
The first line of input is an integer N (N < 1000), that indicates the total number of test cases. Each case is a valid expression in the infix format.
Output
For each test case, print the expression converted to posfix expression.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define EXP_MAX_SIZE 1024
int prec(char operator);
void paraPosfixa(const char *exp, char *out);
int main (void) {
int N;
char infixa[EXP_MAX_SIZE], posfixa[EXP_MAX_SIZE];
scanf("%d\n", &N);
while (N-- > 0) {
fgets(infixa, EXP_MAX_SIZE, stdin);
paraPosfixa(infixa, posfixa);
printf("%s\n", posfixa);
}
return EXIT_SUCCESS;
}
void paraPosfixa(const char *exp, char *out) {
char p[EXP_MAX_SIZE];
int i, o = 0, t = -1;
char c;
for (i = 0; exp[i] != '\n' && exp[i] != '\0'; i++) {
c = exp[i];
if (c == ' ') continue;
if (c == '(') {
p[++t] = c;
}
else if (c == ')') {
while (t > -1 && p[t] != '(') {
out[o++] = p[t--];
}
t--;
}
else if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
out[o++] = c;
}
else {
while (t > -1 && p[t] != '(' && prec(p[t]) >= prec(c)) {
out[o++] = p[t--];
}
p[++t] = c;
}
}
while (t > -1) out[o++] = p[t--];
out[o++] = '\0';
}
int prec(char operator) {
switch (operator) {
case '^':
return 3;
case '*':
return 2;
case '/':
return 2;
case '+':
return 1;
case '-':
return 1;
default:
return 0;
}
}
0 Comentários