Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Printing an Expression Tree with Parentheses in Java

Posted on 2008-10-28
6
Medium Priority
?
3,521 Views
Last Modified: 2013-11-23
I've implemented a postfix-to-infix converter using stacks of expression trees. However, I'm running into a few minor issues that I can't seem to fix.

First, if the postfix expression passed contains two-digit numbers (i.e., 10, 20) as opposed to single-digit numbers or characters (i.e., 1, 5, A, E), the converter doesn't work properly. The reason behind this is because of a check I am making using the isDigit() or isCharacter() methods of the Character class. However, I don't know the correct syntax to check whether there are multiple digits.

My other problem lies in the fact that the parentheses seem to occur in the right spaces; however, the converter unnecessarily adds them around every digit/letter. For example, the input "AB+CD-*" returns (((A )+ (B ))* ((C )- (D ))).

My code is included below--it uses an ExpressionTree class that I created in addition to the PostfixToInfix converter file. I've attached the ExpressionTree class in the same code snippet.
import java.util.*;
 
public class PostfixToInfix {
 
	public static void postfixToInfix (String input)
	{
		Stack<ExpressionTree> treeStack = new Stack<ExpressionTree>();
		
		for (int i = 0; i <input.length(); i++)
		{
			char ch = input.charAt(i);
			if (Character.isDigit(ch))
			{
				treeStack.push(new ExpressionTree(ch, null, null));
			}
			else if (Character.isLetter(ch))
			{
				treeStack.push(new ExpressionTree(ch, null, null));
			}
			else if (ch=='+' || ch=='/' || ch=='*' || ch=='-')
			{
				ExpressionTree right = treeStack.pop();
				ExpressionTree left = treeStack.pop();
				treeStack.push(new ExpressionTree(ch, right, left));
			}
		}
		while (!treeStack.isEmpty())
			ExpressionTree.print(treeStack.pop());
	}
	public static void main(String[] args) {
		postfixToInfix("AB+CD-*");
		System.out.println();
		postfixToInfix("12345++++2010-34*/*");
		//Output should be ((1 + (2 + (3 + (4 + 5))))*((20 - 10) / (3 * 4)))
	}
}
 
//====================EXPRESSION TREE CLASS HERE 
//(May have to Change a call to the print method 
//due to the fact that this is an external file
public class ExpressionTree {
	
	char data;
	ExpressionTree left, right;
	
	public ExpressionTree(char data, ExpressionTree right, ExpressionTree left)
	{
		this.data = data;
		this.right = right;
		this.left = left;
	}
	
 
    public static void print (ExpressionTree tree) {
        if (tree == null) return;
        System.out.print("(");
        print (tree.left);
        
        System.out.print (tree.data + " ");
        print (tree.right);
        System.out.print(")");
    }
}

Open in new window

0
Comment
Question by:paid_tech
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
6 Comments
 
LVL 9

Accepted Solution

by:
mbodewes earned 2000 total points
ID: 22830339
How do you know that 2010 is either a single number or two or three or four numbers? And where should the digits split, always in the middle? You will need something to tell the difference between the numbers. One or multiple white-spaces would do the trick. Then tokenize the input before putting it into the tree.

The great thing about post-fix (which I still hate, it seems to be optimized for machines, not for human beings) is that you don't need parenthesis of course. After building the tree, you will need to walk it and see which operators take precedence and add the parentheses where the lower part of the inverted tree are of lower precedence than the ones on top of it.
0
 
LVL 9

Expert Comment

by:mbodewes
ID: 22891771
Does this help you any or are you still stuck? Please post if you need more assistance.
0
 

Author Comment

by:paid_tech
ID: 22891802
I'm still stuck. I've been working on it all week. I understand the algorithm, just don't know what the proper syntax would be to successfully skip over spaces.

I changed my ExpressionTree class to store String data instead of Character and I'm trying to add them to a temp String in the postfixtoinfix file.

As for parentheses, since the print method is recursive, I don't know how to print around only leaf nodes.

Your suggestions have helped some, but I'm still stuck.
0
Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

 
LVL 9

Expert Comment

by:mbodewes
ID: 22907005
"I changed my ExpressionTree class to store String data instead of Character and I'm trying to add them to a temp String in the postfixtoinfix file."

That's a good start. Try and use a state machine to see where you are at a particular point in time. When you are going out of a name or number, put the String on the stack (for additional niceness, use a StringBuilder and toString(). You might want to create certain token types as well (e.g. operator, number, variable) and store those instead of just the String.

The rank of an expression is that of the operator in the expression. If a child expression has a lower rank (test this before going deeper) then you need to add parentheses.

Please post new code when you get the chance, I don't currently have the time to show some example code myself (unfortunately). I'm trying to create a java implementation of the Skein hash algorithm, and the testing takes loads of time.
0
 

Author Closing Comment

by:paid_tech
ID: 31511038
Thanks for your help. I had to do a lot of debugging with System.out to make sure everything was working out properly, but I ended up implementing it.

Thanks for your input!
0
 
LVL 9

Expert Comment

by:mbodewes
ID: 22918377
Lots of println statements for the Skein hash method as well, and it's working now. Look into (Apache commons or default Java) logging instead of println statements -> you can simply decide to not log later on, and if you need to change or test your application, you simply put it on again. It's pretty easy to learn.

That was a rather tough assignment by the way, tricky to get right. Glad you did get it right in the end.
0

Featured Post

Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Suggested Courses

715 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question