1

I coded up this program which will take an infix notation expression and build a binary tree from it. Right now the only input expression that actually works would be like 2 + 2. I can't seem to figure out at all how to make it handle parenthesis and take in longer expressions such as ( ( 2 + 2 ) * 3 ). For my output I am trying to get it into postfix notation and also evaluate the expression. So right now if I plug in 2 + 2 without the parenthesis my output is 22+ and it evaluates it so it prints 4.

I need to figure out a way for it to print out the output with spaces in between each number and operator and also get it to accept longer expressions with parenthesis. I have no idea right now how to continue from here. Can anyone please help me out?

Thanks!

This is my code:

class ExpressionEvaluator<T> {

    ExpressionEvaluator() {
        Scanner reader = new Scanner(System.in);

        System.out.println("Enter your expression: ");
        String expression = reader.nextLine();    // Reads the expression and trims the spaces.
        expression = expression.replaceAll(" ", "");
        ExpressTree<T> tree = new ExpressTree(expression); // Creates a new binary tree.
    }

    public static void main(String[] args) {
        new ExpressionEvaluator();
    }
}


interface Tree<T> {

    // This is the tree interface with its methods.
    public Node<T> getRoot();

    public void setRoot(Node<T> value);
}


class ExpressTree<T> implements Tree<T> {

    private Node<T> _root;
    private String _value, _expression;
    private Node<T> _treeNode;
    private Stack storage1;
    private Stack<String> storage2;

    public ExpressTree(String expression) {
        expressTreeBuilder(expression);        // Calls the expressTreeBuilder method on the expression.
        postfixTraversal(this.getRoot());
        System.out.println("");
        System.out.println(this.storage2.pop());
    }

    public Node<T> getRoot() {        // Gets the root of the tree.
        return _root;
    }

    public void setRoot(Node<T> _treeNode2) {        // Sets the root which will always be an operator.
        this._root = _treeNode2;
    }

    public boolean isDigit(char value) {    // Method to check if a value is a digit or not.
        if (Character.isDigit(value)) {
            return true;
        } else {
            return false;
        }
    }

    public void expressTreeBuilder(String expression) {

        storage1 = new Stack();    // Stores the nodes.
        storage2 = new Stack<String>();        // Stores the value of the nodes.
        _treeNode = new Node();        // Creates a new node
        _value = null;
        String next = "";

        for (int i = 0; i < expression.length(); i++) {
            char traverse = expression.charAt(i);
            if (i + 1 < expression.length()) {
                next = Character.toString(expression.charAt(i + 1));
            }

            if (traverse == '+') {        // This checks to see the expression is an addition operator.
                Node<T> pop1, pop2;        // It pops the first 2 values from the stack and stores them
                String value1, value2;    // in pop1 and pop2. Then it uses another stack to add them.
                pop1 = (Node<T>) storage1.pop();
                value1 = storage2.pop();    // Stores the right side value.
                value2 = next;    // Stores the left side value.
                _treeNode = new Node();
                _treeNode.setElement(Character.toString(traverse));
                pop2 = new Node();
                pop2.setElement(next);
                pop1.setParent(_treeNode);
                pop2.setParent(_treeNode);
                _treeNode.setLeftSide(pop1);        // Sets the right side of the subtree.
                _treeNode.setRightSide(pop2);        // Sets the left side of the subtree.
                storage1.push(_treeNode);
                storage1.push(pop2);
                int add = (Integer.parseInt(value2) + Integer.parseInt(value1));
                storage2.push(Integer.toString(add));
                this.setRoot(_treeNode);
                i++;
            } else if (traverse == '-') {        // This checks to see the expression is a subtraction operator.
                Node<T> pop1, pop2;        // It pops the first 2 values from the stack and stores them
                String value1, value2;    // in pop1 and pop2. Then it uses another stack to subtract them.
                pop1 = (Node<T>) storage1.pop();
                value1 = storage2.pop();    // Stores the right side value.
                value2 = next;    // Stores the left side value.
                _treeNode = new Node();
                _treeNode.setElement(Character.toString(traverse));
                pop2 = new Node();
                pop2.setElement(next);
                pop1.setParent(_treeNode);
                pop2.setParent(_treeNode);
                _treeNode.setLeftSide(pop1);        // Sets the right side of the subtree.
                _treeNode.setRightSide(pop2);        // Sets the left side of the subtree.
                storage1.push(_treeNode);
                storage1.push(pop2);
                int subtract = (Integer.parseInt(value2) - Integer.parseInt(value1));
                storage2.push(Integer.toString(subtract));
                this.setRoot(_treeNode);
                i++;
            } else if (traverse == '*') {    // This checks to see the expression is a multiplication operator.
                Node<T> pop1, pop2;    // It pops the first 2 values from the stack and stores them
                String value1, value2;    // in pop1 and pop2. Then it uses another stack to multiply them.
                pop1 = (Node<T>) storage1.pop();
                value1 = storage2.pop();    // Stores the right side value.
                value2 = next;    // Stores the left side value.
                _treeNode = new Node();
                _treeNode.setElement(Character.toString(traverse));
                pop2 = new Node();
                pop2.setElement(next);
                pop1.setParent(_treeNode);
                pop2.setParent(_treeNode);
                _treeNode.setLeftSide(pop1);        // Sets the right side of the subtree.
                _treeNode.setRightSide(pop2);        // Sets the left side of the subtree.
                storage1.push(_treeNode);
                storage1.push(pop2);
                int multiply = (Integer.parseInt(value2) * Integer.parseInt(value1));
                storage2.push(Integer.toString(multiply));
                this.setRoot(_treeNode);
                i++;
            } else if (traverse == '(') {

            } else {
                _treeNode = new Node();
                String digits = "";
                while (i < expression.length() && isDigit(expression.charAt(i))) {
                    digits += expression.charAt(i);    // Checks if the value found at the expression is digit
                    if (digits.length() == 1) {
                        break;
                    }
                    i++;
                }

                _treeNode.setElement(digits);        // If it is it will set the element of the node
                storage1.push(_treeNode);        // The node will be pushed onto the stack.
                storage2.push(digits);            // This node will store it's value.
            }
        }
    }

    public void infixTraversal(Node<T> n) {
        if (n != null) {
            infixTraversal(n.getLeftSide());
            System.out.print(n.element() + "");
            infixTraversal(n.getRightSide());
        }
    }

    public void postfixTraversal(Node<T> n) {
        if (n != null) {
            postfixTraversal(n.getLeftSide());
            postfixTraversal(n.getRightSide());
            System.out.print(n.element());
        }
    }
}


class Node<T> {

    public Node<T> _left, _right, _parent;
    private String _element;

    public Node() {
        this._element = null;
        this._left = null;
        this._right = null;
        this._parent = null;
    }

    public String element() {                    // Gets the value of the node.
        return _element;
    }

    public Node<T> getLeftSide() {                // Gets the left side of the node.
        return _left;
    }

    public Node<T> getRightSide() {                // Gets the right side of the node.
        return _right;
    }

    public Node<T> getParent() {                // Gets the parent of the node.
        return _parent;
    }

    public void setElement(String e) {            // Sets the value of the node.
        _element = e;
    }

    public void setLeftSide(Node<T> n) {        // Sets the left side of the node.
        _left = n;
    }

    public void setRightSide(Node<T> n) {        // Sets the right side of the node.
        _right = n;
    }

    public void setParent(Node<T> n) {            // Sets the parent of the node.
        _parent = n;
    }
}
4

2 回答 2

3

You will need a proper algorithm for converting your infix expression into a postfix expression. Once you have the expression in postfix it's a fairly easy matter of constructing a parse tree or evaluate the expression outright. A classic algorithm is the Shunting-yard algorithm, which is explained in quite extensive detail on wikipedia.

Once the algorithm to postfix is completed you do no longer have to worry about parathesis or operator precedence. It's just a stack of values and popping and pushing results.

于 2012-02-26T14:03:22.303 回答
0

您的问题有几个不同的问题:

1)解析表达式并将其分解成一棵树。为此,您需要一个词法分析器(或标记器),甚至是一个简单的,它具有优先级、括号等。

2)转换/评估你的树。有一些很好的经典算法。

3) 打印结果(我怀疑一旦你完成了第 2 部分,这相当简单;只需在正确的位置添加正确的空格和括号)。

我建议阅读一些关于所有这些的现有文章,例如:

于 2012-02-26T14:32:26.240 回答