留着当个模板用,在BNU上AC,在LA上RE……可能是java的提交方式不同???
数和运算符各开一个栈。
表达式从左到右扫一遍,将数存成大数,遇到数压在 数的栈,运算符压在 运算符的栈,每当遇到右括号时,弹出 数的栈 的栈顶头两个元素,弹出 运算符的栈 顶的头一个元素,进行运算,将运算结果压回 数的栈 中。最后输出栈顶元素。
运算过程中把不符合情况的判掉。
我写的第二个java的题,竟然1A……这世界太不可思议了= =
import java.util.*; import java.math.BigInteger; public class Main { static Scanner in=new Scanner(System.in); static int MAXN = 200010; static char[] ss = new char[MAXN]; static char[] oper = new char[100]; static BigInteger[] shu = new BigInteger[100]; static BigInteger TEN = BigInteger.valueOf(10); static BigInteger ZERO = BigInteger.valueOf(0); static BigInteger MAXX = new BigInteger("999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"); public static String init() { int i, j, top, len; if ( in.hasNext() == false ) return new String("End"); String str = new String(); String tmp = new String(); top = 0; do { tmp = in.next(); len = tmp.length(); ss = tmp.toCharArray(); for ( i = 0; i < len; ++i ) { if ( ss[i] == '(' ) ++top; if ( ss[i] == ')' ) --top; } str = str + tmp; }while ( top != 0 ); return str; } public static boolean GetOper( char a ) { switch(a) { case '+': case '-': case '*': case '/': return true; default: return false; } } public static void main(String[] args) { // TODO Auto-generated method stub String Prob; boolean flag, GetOp; int len, i, j, top ; int topOp, topShu; BigInteger val = BigInteger.valueOf(0); BigInteger tmp1, tmp2; char[] valStr = new char[100]; int valStrlen = 0; while ( (Prob = init()).compareTo("End") != 0 ) { flag = true; len = Prob.length(); ss = Prob.toCharArray(); top = 0; topShu = 0; topOp = 0; val = ZERO; valStrlen = 0; int first = 0; for ( i = 0; flag && i < len; ++i ) { if ( ss[i] >= '0' && ss[i] <= '9' ) { valStr[ valStrlen++ ] = ss[i]; if ( valStrlen > 90 ) { flag = false; break; } if( first == 0 ) first = 1; } else { if ( ss[i] == '(' ) { if ( first == 0 ) first = 2; ++top; } else if ( ss[i] == ' ' ) continue; else { if ( valStrlen != 0 ) { val = ZERO; for ( j = 0; j < valStrlen; ++j ) { val = val.multiply(TEN); val = val.add( BigInteger.valueOf( valStr[j]-'0' ) ); } //System.out.println(val); //System.out.println("------------"); valStrlen = 0; shu[ ++topShu ] = val; } if ( ss[i] == ')' ) { --top; tmp2 = shu[ topShu ]; tmp1 = shu[ --topShu ]; //System.out.println("******"); //System.out.println(topShu); //System.out.println("++++++"); //System.out.println(tmp1); //System.out.println(tmp2); switch( oper[ topOp ] ) { case '+': tmp1 = tmp1.add(tmp2); break; case '-': tmp1 = tmp1.subtract(tmp2); break; case '*': tmp1 = tmp1.multiply(tmp2); break; case '/': if ( tmp2.compareTo(ZERO) == 0 ) { flag = false; break; } tmp1 = tmp1.divide(tmp2); break; } //System.out.println(tmp1); //System.out.println("++++++"); --topOp; if ( tmp1.compareTo(MAXX) > 0 || tmp1.compareTo(ZERO) < 0 ) { flag = false; break; } shu[ topShu ] = tmp1; //System.out.println(tmp1); val = ZERO; } else if ( ( GetOp = GetOper(ss[i]) ) == true ) { oper[ ++topOp ] = ss[i]; } } } } //System.out.println(topShu); //System.out.println("####"); //for ( i = 0; i <= topShu; ++i ) //System.out.println(shu[i]); if ( flag ) { if ( first == 2 ) System.out.println(shu[1]); else { val = ZERO; for ( j = 0; j < valStrlen; ++j ) { val = val.multiply(TEN); val = val.add( BigInteger.valueOf( valStr[j]-'0' ) ); } //System.out.println(val); //System.out.println("------------"); if ( val.toString().length() > 90 ) System.out.println("Error"); else System.out.println( val ); } } else System.out.println("Error"); } } }