This blog is accompanied site of http://j2megamer.blogspot.com. Here I will post various source codes. Related to software and computer science. Its exclusively for code posting.
Site Menu
Previous Posts
- Google Code Jam 2004 Practice Room 500 Point
- Google Code Jam 2004 Practice Room 250 Point
- SRM 209 DIV 2 - 500 pts
- First Post
Gaming Links
Powered By
Sunday, September 05, 2004
DevX September 2004 Challenge Level 2, Difficult
Problem Statement
There are several software packages that typeset mathematical expressions. For example,
the expression "(31+24/12)/(5+6) + 16" might be typeset like this:
" 24 "
" 31 + ---- "
" 12 + 16"
"----------- "
" 5 + 6 "
Write a method that takes such a typeset mathematical expression and evaluates it,
returning the numerical value of the expression. If given the expression above, your
method should return 19.
The input expression will be a two-dimensional array of characters, given as a String
[]. Expressions will be built out of other expressions, rectangular portions of the
given array. Every expression will be in one of three forms:
integer constant: The expression will be exactly one character high, will consist
solely of digits, and will not contain any leading zeros.
addition: The expression will be constructed out of left and right subexpressions.
Zero or more rows of spaces will be added above and below each subexpression and
will give them the same height. Three columns of that height will be placed between
them, containing all spaces, except for a single '+' character anywhere in the
middle column.
division: The expression will be constructed out of top and bottom subexpressions.
One or more columns of spaces will be added to the left and right of each
subexpression to give them the same width. One row consisting entirely of '-'
characters will be placed between them.
Example:
The expression above has one column (column 12) with all spaces except for a
single '+' character. Therefore, this expression is built by adding two
subexpressions together. If we take the regions to the left and right of column 12,
and remove all rows and columns on the edges containing only spaces, we get the
following two subexpressions:
" 24 "
" 31 + ---- "
" 12 " and "16"
"-----------"
" 5 + 6 "
The right subexpression contains only digits, so it evaluates to the value 16. The
left subexpression has one row (row 3) with all '-' characters. Therefore, this
expression is built by dividing two subexpressions. If we take the regions above and
below row 3, and remove all rows and columns on the edges containing only spaces, we
get the following two subexpressions:
" 24 "
"31 + ----" and "5 + 6"
" 12 "
Here, both subexpressions are addition. The right subexpression adds "5" and "6",
resulting in the value 11. The left subexpression is built by adding two more
subexpressions:
" 24 "
"31" and "----"
" 12 "
The left side evaluates to the value 31, and the right side evaluates to the
division of the subexpressions "24" and "12". Working back up, 24 divided by 12 is
2, added to 31 is 33, divided by 11 is 3, plus 16 is 19.
import java.util.*;
public class Untypeset
{
public static void main( String s[] )
{
String []input =
{ " 625 + 0 ",
"-----------------",
" 5 " };
int result = evaluate( input );
System.out.println( "Result is:" + result );
}
public static int evaluate(String[] expression)
{
Stack myStack = new Stack();
myStack.push( expression );
String key = "0123456789 ";
String plus[] = {"P"
};
String div[] = {"D"
};
Stack finalStack = new Stack();
_L1:
while( myStack.size() != 0 )
{
String expr[] = (String[])myStack.pop();
int test1 = 0;
int validindex = 0;
for( int count = 0; count < expr.length; count++ )
{
if( expr[ count ].trim().length() == 0 )
{
test1++;
}
else
{
validindex = count;
}
}
if( expr.length == 1 )
{
boolean insert = true;
for( int t = 0; t < expr[0].length(); t++ )
{
if( expr[0].charAt( t ) == '+' || expr[0].charAt( t ) == '-' )
{
insert = false;
break;
}
}
if( insert )
{
finalStack.push( expr[ 0 ] );
}
}
else if( (expr.length - test1) == 1 )
{
if( !expr[ validindex ].equals( "P" ) && !expr[ validindex ].equals( "D" ) )
{
boolean insert = true;
for( int t = 0; t < expr[validindex].length(); t++ )
{
if( expr[validindex].charAt( t ) == '+' || expr[validindex].charAt( t ) == '-' )
{
insert = false;
break;
}
}
if( insert )
{
finalStack.push( expr[ validindex ] );
}
}
}
int vlen = expr.length;
int hlen = expr[0].length();
StringTokenizer st;
for( int i = 0; i < hlen; i++ )
{
String temp = "";
for( int j = 0; j < vlen; j++ )
{
temp += expr[ j ].charAt(i);
}
st = new StringTokenizer( temp, key );
if( st.countTokens() == 1 && st.nextToken().equals("+") ) //theres a +
{
//seperate into two and push on the stack
String one[] = new String[ expr.length ];
String two[] = new String[ expr.length ];
for( int k = 0; k < vlen; k++ )
{
one[ k ] = two[ k ] = "";
one[ k ] = expr[ k ].substring( 0, i );
two[ k ] = expr[ k ].substring( i + 1, hlen );
}
boolean stest = true;
if( one.length == 1 && two.length == 1 )
{
for( int ione = 0; ione < one[0].length();ione++ )
{
if( one[0].charAt( ione ) == '+' || one[0].charAt( ione ) == '-' )
{
stest = false;
break;
}
}
for( int itwo = 0; itwo < two[0].length();itwo++ )
{
if( two[0].charAt( itwo ) == '+' || two[0].charAt( itwo ) == '-' )
{
stest = false;
break;
}
}
}
if( one.length == 1 && two.length == 1 && stest )
{
String sone = one[ 0 ].trim();
String stwo = two[ 0 ].trim();
int ione = Integer.parseInt( sone );
int itwo = Integer.parseInt( stwo );
String ans = "" + (ione + itwo);
String aans[] = { ans
};
myStack.push( aans );
}
else
{
myStack.push( one );
myStack.push( plus );
myStack.push( two );
}
continue _L1;
}
} //+ are done
//now horizontal split for /
for( int i = 0; i < vlen; i++ )
{
String temp = "";
for( int j = 0; j < hlen; j++ )
{
temp += expr[ i ].charAt(j);
}
boolean test = true;
temp = temp.trim();
for( int count = 0; count < temp.length(); count++ )
{
if( temp.charAt( count ) != '-' )
{
test = false;
break;
}
}
if( temp.length() == 0 )
{
test = false;
}
if( test ) //theres a +
{
String one[] = new String[ i ];
String two[] = new String[ vlen - i - 1 ];
for( int k = 0; k < i; k++ )
{
one[ k ] = "";
one[ k ] = expr[ k ];
}
for( int k = i + 1; k < vlen; k++ )
{
two[ k - i - 1 ] = "";
two[ k - i - 1 ] = expr[ k ];
}
boolean stest = true;
if( one.length == 1 && two.length == 1 )
{
for( int ione = 0; ione < one[0].length();ione++ )
{
if( one[0].charAt( ione ) == '+' || one[0].charAt( ione ) == '-' )
{
stest = false;
break;
}
}
for( int itwo = 0; itwo < two[0].length();itwo++ )
{
if( two[0].charAt( itwo ) == '+' || two[0].charAt( itwo ) == '-' )
{
stest = false;
break;
}
}
}
if( one.length == 1 && two.length == 1 && stest )
{
String sone = one[ 0 ].trim();
String stwo = two[ 0 ].trim();
int ione = Integer.parseInt( sone );
int itwo = Integer.parseInt( stwo );
String ans = "" + ione/itwo;
String aans[] = { ans
};
myStack.push( aans );
}
else
{
myStack.push( one );
myStack.push( div );
myStack.push( two );
}
continue _L1;
}
}
}
while( finalStack.size() > 1 )
{
while( finalStack.size() >= 3 )
{
String one = (String)finalStack.pop();
String two = (String)finalStack.pop();
String three = (String)finalStack.pop();
if( two.trim().equals("P") )
{
int ione = Integer.parseInt( one.trim() );
int itwo = Integer.parseInt( three.trim() );
finalStack.push( "" + (ione + itwo ) );
}
else if( two.trim().equals("D") )
{
int ione = Integer.parseInt( one.trim() );
int itwo = Integer.parseInt( three.trim() );
finalStack.push( "" + (ione / itwo ) );
}
}
}
return Integer.parseInt( (String)finalStack.pop() );
}
}
- posted by Max @ 11:06 AM
