E07 Notação polonesa reversa
Faça o Web Exercise 1.3.15, Infix to postfix with precedence order:
https://algs4.cs.princeton.edu/13stacks/
Seu programa deve aceitar expressões infixas como as expressões a seguir:
4 ^ ( 7 / 2 ) * 1 - ( 6 + 7 )
( 8 * 6 * ( 8 - 2 ) - ( ( 4 + 8 ) * 3 + 3 ^ 5 ) ) / 5 ^ 7
2 ^ 3 ^ 4
As saídas para os exemplos acima devem ser
4 7 2 / ^ 1 * 6 7 + -
8 6 * 8 2 - * 4 8 + 3 * 3 5 ^ + - 5 7 ^ /
2 3 4 ^ ^
Seu programa deve chamar-se RPN.java. Com os exemplos acima, seu programa deve ter esse comportamento:
$ echo "4 ^ ( 7 / 2 ) * 1 - ( 6 + 7 )" | java-algs4 RPN
4 7 2 / ^ 1 * 6 7 + -
$ echo "( 8 * 6 * ( 8 - 2 ) - ( ( 4 + 8 ) * 3 + 3 ^ 5 ) ) / 5 ^ 7" | java-algs4 RPN
8 6 * 8 2 - * 4 8 + 3 * 3 5 ^ + - 5 7 ^ /
$ echo "2 ^ 3 ^ 4" | java-algs4 RPN
2 3 4 ^ ^
$
Operadores a serem considerados. Seu programa deve conhecer os operadores "+", "-", "*", "/", "%" e "^". O operador "^" representa a exponenciação: "a^b" significa \(a^b\). Os operandos são inteiros, que você pode supor positivos.
Precedência e associatividade. A precedência e a associatividade dos operadores é a usual. Veja, por exemplo,
https://introcs.cs.princeton.edu/java/11precedence/
Note que a associatividade de "^" é da direita para a esquerda.
Expressões aleatórias. Você pode experimentar seu programa com as expressões infixas geradas por RandomExpression.java. RandomExpression.java executado com argumentos $M$, $N$ e $s$ gera uma expressão com $M$ operadores, envolvendo operandos que variam de $1$ a $N$. O argumento $s$ é usado como a semente do gerador de números aleatórios. Ademais, se mais um argumento é dado, não apenas uma expressão é gerada, mas seu valor também é calculado. (O valor calculado é enviado para stderr e não stdout, e portanto é possível usar piping para processar a saída de RandomExpression.java usando RPN.java; veja exemplos abaixo.)
Observação. Quando um quarto argumento é dado para se obter o valor da expressão, os operadores "/" e "%" não são usados, para evitar expressões que envolvem divisão por $0$.
Exemplos de execução
$ java-algs4 RandomExpression 5 9 128
1 ^ ( 6 / 4 ) * 1 - ( 5 + 9 )
$ java-algs4 RandomExpression 10 9 128
9 * 7 ^ ( 7 / ( 9 % 2 ) % ( 5 % 7 % 8 - 6 ) ) - ( 4 - 5 )
$ java-algs4 RandomExpression 20 9 128
( 7 / ( 9 % 2 ) % ( 5 % 7 % 8 - 6 ) + ( 9 / 2 - 1 ) ) ^ ( 6 % 4 ) * ( 3 / ( 7 - 2 ) * ( 8 - 4 - 8 * 8 ) ) - 1 * 6
$ java-algs4 RandomExpression 5 9 2022 .
( 5 + 5 ^ 4 ) ^ ( 1 * 1 + 7 )
[Value of random expression: 4707247612753076480]
$ java-algs4 RandomExpression 10 9 2022 .
( 5 ^ ( 7 + 6 ) + ( 6 ^ 1 + ( 4 + ( 8 - 1 ) ) ) ) ^ ( 4 ^ ( 6 ^ 6 ) )
[Value of random expression: 1]
$ java-algs4 RandomExpression 20 9 2022 .
( 5 ^ ( 7 + 6 ) + ( 6 ^ 1 + ( 4 + ( 8 - 1 ) ) ) ) ^ ( ( 8 + 6 ) ^ ( ( 7 + 5 ) * ( 8 - 7 ) ^ 3 * ( ( 6 * 5 + ( 8 * 6 - 5 ) ) * 8 ) ) )
[Value of random expression: 1]
$
Avaliador de expressões pós-fixas. O programa EvaluatePostfix.java abaixo pode ser usado para avaliar as expressões pós-fixas computadas por seu programa RPN.java.
$ java-algs4 RandomExpression 5 4 128 . | java-algs4 RPN | java-algs4 EvaluatePostfix
[Value of random expression: 13]
Value of postfix expression: 13
$ java-algs4 RandomExpression 10 4 128 . | java-algs4 RPN | java-algs4 EvaluatePostfix
[Value of random expression: 0]
Value of postfix expression: 0
$ java-algs4 RandomExpression 100 4 128 . | java-algs4 RPN | java-algs4 EvaluatePostfix
[Value of random expression: 3]
Value of postfix expression: 3
$ java-algs4 RandomExpression 1000 4 128 . | java-algs4 RPN | java-algs4 EvaluatePostfix
[Value of random expression: -1623076]
Value of postfix expression: -1623076
$
Naturalmente, o valor computado por RandomExpression.java para a expressão gerada e o valor computado por EvaluatePostfix.java devem coincidir. Mais dois exemplos:
$ echo "4 ^ 3 ^ 2" | java-algs4 RPN | java-algs4 EvaluatePostfix
Value of postfix expression: 262144
$ echo "( 4 ^ 3 ) ^ 2" | java-algs4 RPN | java-algs4 EvaluatePostfix
Value of postfix expression: 4096
$
Entrega. Entregue apenas seu programa RPN.java.
- 23 maio 2022, 22:32 PM
- 23 maio 2022, 22:32 PM