深圳两个上机题之我的解答

在些声明此两题是论坛上一人的上机试题,解答是本人写的!

原题如下:
第一个：写一个方法，参数传递一个字符串表达式，返回结果为表达式计算结果。如：传递表达式"1+2*3+6-2/2"返回计算的结果。

第二个：9个数1-9组成三个数，如：327 654 981，每个数字只能用一次，每三个数字组成一个新的数字，第二个数是第一个数的两倍，第三个数是第一个数的三倍，用程序实现。

关于第一题我的解答如下:

package com.jishi.shenzheng;

import java.util.Stack;

//解决的第一个BUG为当遇到的运算符出栈时，要直到栈空或栈顶元素的优先组小于当前字符时才能执行入栈操作
//解决的第二个BUG为开妈没有考虑在字符串中处理多位数
public class First {

	// 对表达式进行求值运算
	public static double evaluation(String expression) {
		expression = pretreatment(expression);
		// 引入一个字符栈，用来存放在表达式中出现过的运算符
		Stack<Character> Chstack = new Stack<Character>();
		// 引入一个数字栈，用来存放在表达式中出现过的运算数
		Stack<Double> Dostack = new Stack<Double>();
		// 扫描表达式
		for (int i = 0; i <= expression.length() - 1; i++) {
			 Character ch = expression.charAt(i);
			// 处理表达式中出现的数字
			if (Character.isDigit(ch)) {  //其中扫描到数字时并不是这么容易处理，要考虑多们数的情况
				StringBuilder sb=new StringBuilder();
				sb.append(ch);
				//这个while循环用来处理字符串中的实数或多位数
				while((i+1<=expression.length()-1)&&(Character.isDigit(expression.charAt(i+1))||expression.charAt(i+1)=='.')){
				   sb.append(expression.charAt(i+1));
					i++;
				}
			 	Dostack.push(Double.parseDouble(sb.toString()));
			} else { // 处理表达式中出现的运算符
				if (ch == '(') {
					Chstack.push(ch);
				} else if (ch == ')') { // 遇到右括号的情况较为复杂，稍后考虑
                     do{
                    	char operator=Chstack.pop(); 
                    	if(operator=='(') break;
                    	double d1=Dostack.pop();
                    	double d2=Dostack.pop();
                    	double answer=operation(d1,d2,operator);
                    	Dostack.push(answer);
                    	ch=operator;
                     }while(ch!='(');  //直到栈中弹出左括号为止
                  } else { // 遇到的是普通的运算符
					if (Chstack.isEmpty()) { // 栈空的话直接入栈
						Chstack.push(ch);
					} else { // 栈非空则根据优先级入栈
                        int uppriority=priority(ch);
                        int downpriority=priority(Chstack.peek());
                        if(downpriority==0){ //如果此时栈顶为左括号则直接入栈
                        	Chstack.push(ch);
                        }else{
                        	int priority=uppriority-downpriority;
                        	if(priority<=0){ //如果新入本的运算符优先级比栈顶运算符低,此处处理稍微麻烦一点点
                        		do{   //新加入的do_while循环是为了解决第一次遇到的Bug的
                        	    char operator=Chstack.pop();
                        	    //Chstack.push(ch); //此时的栈顶元的优先仍需判断,此时入栈为时尚早
                        		double d1=Dostack.pop();
                        		double d2=Dostack.pop();
                        		double answer=operation(d1,d2,operator);
                        		Dostack.push(answer);
                        		if(Chstack.empty()) break;
                        		downpriority=priority(Chstack.peek());
                        		if(downpriority==0) break;
                         	    priority=uppriority-downpriority;
                        		}while(priority<=0);
                        		Chstack.push(ch);
                        	}else{//如果新入本的运算符优先级比栈顶运算符高则直接入栈即可
                        		Chstack.push(ch);
                        	}
                        }
					}
				}
			}
		}
		
		//返回栈顶元素，即为表达式结果
	    while(!Chstack.empty()){
	    	char operator=Chstack.pop();
    		double d1=Dostack.pop();
    		double d2=Dostack.pop();
    		double answer=operation(d1,d2,operator);
    		Dostack.push(answer);
	    }
	    return Dostack.pop();
	}

	// 对表达式进行预处理，主要是为了解决负数运算问题
	public static String pretreatment(String expression) {
		// 如果负号出现在表达式首部，则易处理在前面加0即可
		if (expression.charAt(0) == '-') {
			expression = "0" + expression;
		}
		// 处理负数出现在非首部的情况
		expression = expression.replace("(-", "(0-");
		return expression;
	}

	//判断运算符的优先级
	public static int priority(char ch) {
		switch (ch) {
		case '+':		return 1;
		case '-':       return 1;
		case '*':       return 2;
		case '/':       return 2;
		default:    	return 0;
		}
	}
	
	//处理简单的运算
    public static double operation(double d1,double d2,char ch){
        switch(ch){
        case '+':return d1+d2;
        case '-':return d2-d1;
        case '*':return d1*d2;
        case '/':return d2/d1;
        default:return 0;
        }
    }
	
	public static void main(String[] args) {
		//测试表达式求值
		System.out.println("2.5+3="+First.evaluation("2.5+3"));
		System.out.println("(2.5+2)*(2-4)="+evaluation("(2.5+2)*(2-4)"));
		System.out.println("-3+(-4)+(5*2+(-3+4)+6)/4+8="+evaluation("-3+(-4)+(5*2+(-3+4)+6)/4+8"));
		System.out.println("3+5-6*3+4/2="+evaluation("3+5-6*3+4/2"));
		 
	   
	}

}
运行结果如下:
2.5+3=5.5
(2.5+2)*(2-4)=-9.0
-3+(-4)+(5*2+(-3+4)+6)/4+8=5.25
3+5-6*3+4/2=-8.0

关于第二题我的解答如下:

package com.jishi.shenzheng;
//经典回溯思想
public class Second {
   public static void dfs(int[] a,int n){
		if(n>a.length-1){
			int s1=a[0]*100+a[1]*10+a[2];
			int s2=a[3]*100+a[4]*10+a[5];
			if(s2!=s1*2) return;
			int s3=a[6]*100+a[7]*10+a[8];
			if(s3==3*s1){
				System.out.println(s1+";"+s2+";"+s3);
			}
		}else{
			for(int i=1,j;i<=9;i++){
				for(j=0;j<n;j++){
					if(i==a[j]){
						break;
					}
				}
				if(j<n){
					continue;
				}else{
					a[n]=i;
				    dfs(a,n+1);
				}
			}
		}
	}
	
	public static void main(String[] args){
		int[] a=new int[9];
		dfs(a,0);
	}
	
}
运行结果如下:
192;384;576
219;438;657
273;546;819
327;654;981