Java Reference
In-Depth Information
figure 11.13
Infix to postfix
conversion
Infix:
1 - 2 ^ 3 ^ 3 - ( 4 + 5 * 6 ) * 7
^
^
-
^
1
2
3
^
-
^
^
-
3
-
-
-
2
1
^
^
-
3
+
(
-
+
+
(
-
5
3
^^-
4
5
(
-
(
(
-
4
-
-
*
+
(
-
*
*
+
(
-
6
6
* +
7
* -
*
-
*
*
-
7
-
)
Postfix:
1 2 3 3 ^ ^ - 4 5 6 * + 7 * -
Figure 11.14 shows the
Evaluator
class skeleton, which is used to process
a single string of input. The basic evaluation algorithm requires two stacks.
The first stack is used to evaluate the infix expression and generate the postfix
expression. It is the stack of operators declared at line 34. An
int
represents
different kinds of tokens, such as
PLUS
,
MINUS
, and so on. These constants are
shown later. Rather than explicitly outputting the postfix expression, we send
each postfix symbol to the postfix machine as it is generated. Thus we also
need a stack that stores operands; the postfix machine stack is declared at
line 35. The remaining data member is a
StringTokenizer
object used to step
through the input line.
As was the case with the balanced symbol checker, we can write a
Tokenizer
class that can be used to give us the token sequence. Although we could reuse
code, there is in fact little commonality, so we write a
Tokenizer
class for this
application only. Here, however, the tokens are a little more complex because, if
we read an operand, the type of token is
VALUE
, but we must also know what the
value is that has been read. To avoid confusion we name the class
EvalTokenizer
and make it nested. Its placement is shown at line 22; its implementation, along
with the nested
Token
class, is shown in Figure 11.15. A
Token
stores both a token
type, and if the token is a
VALUE
, its numeric value. Accessors can be used to obtain
information about a token. (The
getValue
method could be made more robust by
signaling an error if
type
is not
VALUE
.) The
EvalTokenizer
class has one method.
We need two
stacks: an operator
stack and a stack
for the postfix
machine.
Search WWH ::
Custom Search