Here, the left operand of the multiplication operator is the subexpression 5 + 7 and its right operand is the subexpression 18 - 10. Meanwhile, the left operand of the division operator is the subexpression (5 + 7) * (18 - 10) and its right operand is the subexpression 2.
An alternative way of writing expressions, called prefix form, places each operator before (i.e., to the left of) its two operands. This may seem unnatural, but it has the advantage that parentheses are never needed. Below are some examples that show expressions in infix form and their equivalents in prefix form.
| Infix form | Prefix form |
|---|---|
| 5 | 5 |
| 3 + 6 | + 3 6 |
| 3 + (7 - 4) | + 3 - 7 4 |
| (3 + 6) * (7 - 4) | * + 3 6 - 7 4 |
| 2 + (6 + 4) / 5 | + 2 / + 6 4 5 |
| 12 + 3 * (7 - 16 / 8) | + 12 * 3 - 7 / 16 8 |
| ((12 + 3) * 7 - 16) / 8 | / - * + 12 3 7 16 8 |
| (12 + 3) * 7 - (6 + 15 / 5) | - * + 12 3 7 + 6 / 15 5 |
-
/ \
/ \
/ \
* +
/ \ / \
+ 7 6 ÷
/ \ / \
12 3 15 5
|
Suppose that you were to print the labels in the nodes of the tree so that every node's label was printed before those in its two subtrees, with the labels in each node's left subtree being printed before those in its right subtree. The result would be the prefix expression corresponding to the tree.
Meanwhile, if you were to print the labels so that every node's label was printed after those in its left subtree but before those in its right subtree, and you added parentheses where necessary (to account for the PEMDAS (i.e., operator precedence) rules), you would obtain the infix form of the same expression.
Perhaps surprisingly, it is easy to check a prefix expression for syntactic validity. Specifically, expression E is valid if and only if
In other words, if you were to scan a prefix expression from left to right, keeping track of the difference between how many numerals and how many operators you encountered along the way, that difference would be zero or negative the whole way, except upon taking account of the last token, at which point the numerals would exceed the operators by one.
Indeed, every occurrence of a token within a prefix expression E is at the beginning of some subexpression F within E. To find the end of F, scan to the right until the number of occurrences of numerals in F exceeds that of operators.
evaluate(String expr):
stk = empty stack
elem = first token of expr
while (elem != null) {
if (elem is an operator)
{ stk.push(elem) }
else { // elem must be a numeral
if (stk is empty or top of stk is an operator) {
stk.push(elem)
elem = next token in expr (or null if there is none)
}
else {
// The numeral at the top of the stack is the left operand
// of the operator directly under it on the stack.
// The operator's right operand is elem.
leftOperand = stk.pop()
op = stk.pop()
elem = leftOperand op elem
}
}
}
// The lone item remaining on the stack is the result.
return stk.topOf()
|
$ java PrefixExprEvalApp input.txt > 5 5 > + 3 6 9 > + 3 - 7 4 6 > * + 3 6 - 7 4 27 > + 2 / + 6 4 5 4 > + 12 * 3 - 7 / 16 8 27 > / - * + 12 3 7 16 8 11 > - * + 12 3 7 + 6 / 15 5 96 > * + 1 2 * - + 12 9 / 13 + 4 5 6 360 > * 3 hello - 6 9 Invalid token: "hello" Invalid: Too few int literals wrt operators. <---- That is not a valid prefix expression > * + 4 5 - 2 5 8 + - Invalid: Proper prefix has more int literals than operators <---- That is not a valid prefix expression > * 4 - 2 Invalid: Too few int literals wrt operators. <---- That is not a valid prefix expression > Goodbye. |
While the pseudocode algorithm shown above is fine, for what it is, some significant refinements will be necessary to translate it into working Java code. One issue is that the algorithm blurs the distinction between numerals and numbers.1 What, for example, is the data type of the variable elem? As for the stack, are the items being stored on it operators and numerals, or are they operators and numbers?
Because both operators and numerals are naturally considered to be character strings, it would seem that a good way to resolve the second question is for the stack to hold values of type String. Any conversions necessary between numerals and numbers would be handled after each time the stack is popped (to convert the popped numeral into the number it represents) and before each push (to convert a number into the numeral to be pushed).
Suppose that s is of type String and has the form of an integer literal (e.g., "567"). Then the method call Integer.parseInt(s) yields the corresponding value of type int. Meanwhile, if k is of type int, then both String.valueOf(k) and "" + k yield the corresponding value of type String.
As for the stack itself, you are highly encouraged to make use of Java's Stack class, which is in the package java.util. You will notice that its methods are named a little differently from what was discussed in lecture.
As for how to treat a given string as a sequence of tokens separated by whitespace, the most obvious way is to use a Scanner object. If s is a string, the expression new Scanner(s) produces a Scanner that can sequentially "read" the tokens in s, using its next() method repeatedly. Also, the hasNextInt() method tells you whether the next yet-to-be-consumed token is in the form of an integer literal. If it is, the nextInt() method can be used to read it, while at the same time converting it to a value of type int.
Another option for processing the tokens in a given expression is to first apply the split() method to form an array, each element of which holds one of the tokens of the given expression. Then you can iterate through the array elements. This approach might lead you to include this line of code:
The argument passed to the split() method is a regular expression denoting any non-empty sequence of whitespace characters (which includes the space, tab, and newline characters). Its purpose is to describe on what basis to distinguish the tokens in a string from the characters appearing in between them.