Java数据结构的题目
求多项式3x4-6x2+5x-10加上多项式-3x5+7x4+x3+6x2的结果
求代码 谢谢
[解决办法]
思路：
建立一个类，具有系数和次数两种属性；先把次数作为关键字，使得两个多项式排序成为两个有序数组；接下来就是归并有序数组的问题了。
代码你自己实现吧，这是掌握顺序表的必会题，也是学习二路归并排序的基础。
(如果还想锻炼一下的话，自己用正则表达式实现“自动取得多项式的所有的系数和次数”)
[解决办法]
public class PostFix {
public static String postFix(String expression) {
CS401StackLinkedListImpl<Character> operandStack = new CS401StackLinkedListImpl<Character>();
String postfix = "";
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
Character temp;
switch (c) {
case ' ':
break;
case '+':
case '-':
while (operandStack.size() != 0) {
temp = operandStack.pop();
if (temp == '(') {
operandStack.push(temp);
break;
}
postfix += " " + temp;
}
operandStack.push(c);
postfix += " ";
break;
case '*':
case '/':
while (operandStack.size() != 0) {
temp = operandStack.pop();
if (temp == '('
[解决办法]
temp == '+'
[解决办法]
temp == '-') {
operandStack.push(temp);
break;
}
postfix += " " + temp;
}
operandStack.push(c);
postfix += " ";
break;
case '(':
operandStack.push(c);
break;
case ')':
while (operandStack.size() != 0) {
temp = operandStack.pop();
if (temp == '(') {
break;
}
postfix += " " + temp;
}
break;
default:
postfix += c;
break;
}
}
while (operandStack.size() != 0) {
postfix += " " + operandStack.pop();
}
return postfix;
}
public static int calculateArithmeticExp(String postfix) {
CS401StackLinkedListImpl<Integer> stack = new CS401StackLinkedListImpl<Integer>();
String[] strings = postfix.split(" ");
for (int i = 0; i < strings.length; i++) {
String temp = strings[i].trim();
if (temp == "")
continue;
else if (temp.matches("\\d+")) {
stack.push(Integer.parseInt(temp));
} else {
int x = stack.pop();
int y = stack.pop();
if (temp.equals("+"))
stack.push(x + y);
else if (temp.equals("-"))
stack.push(y - x);
else if (temp.equals("*"))
stack.push(x * y);
else if (temp.equals("/"))
stack.push(y / x);
}
}
return stack.pop();
}
}
public static int countString(String s){
System.out.println(s);
int num = 0 ;
String[] ss =s.split("[\\+\\-\\*/\\(\\)]") ;
if( ss.length>2){
int si = 0 ;
if( (si=s.indexOf("("))!=-1){
num =countString(s.substring(si+1 , s.indexOf(")")));
num =countString(s.substring(0 , si)+num + s.substring(s.indexOf(")")+1));
}else if((si=s.replaceAll("[\\*/]", ",").indexOf(","))!= -1 ){
int statr = s.substring(0, si).replaceAll("[\\+\\-\\*/\\(\\)]", ",").lastIndexOf(",") ;
System.out.println(si);
int end = s.substring( si+1).replaceAll("[\\+\\-\\*/\\(\\)]", ",").indexOf(",") ;
num =countString(s.substring(statr==-1?0:statr+1, end==-1?s.length():si+end+1));
num =countString(s.substring(0 , statr==-1?0:statr+1)+num + s.substring(end==-1?s.length():si+end+1));
}else if((si=s.replaceAll("[\\+\\-]", ",").indexOf(","))!= -1 ){
if(si==0){
num = countString("&"+s.substring(1) );
}else{
int statr = s.substring(0, si).replaceAll("[\\+\\-\\*/\\(\\)]", ",").lastIndexOf(",") ;
int end = s.substring( si+1).replaceAll("[\\+\\-\\*/\\(\\)]", ",").indexOf(",") ;
num =countString(s.substring(statr==-1?0:statr+1, end==-1?s.length():end+2));
num = countString(s.substring(0 , statr==-1?0:statr+1)+num + s.substring(end==-1?s.length():end+2));
}
}
}else{
int index =s.replaceAll("[\\+\\-\\*/\\(\\)]", ",").indexOf(",") ;
if(index!=-1){
String s2 =s.substring(index,index+1) ;
if(ss[0].substring(0, 1).equals("&"))
ss[0] ="-"+ ss[0].substring(1) ;
if(s2.equals("*"))
num = new Integer(ss[0]) * new Integer(ss[1]) ;
if(s2.equals("/"))
num = new Integer(ss[0]) / new Integer(ss[1]) ;
if(s2.equals("+"))
num = new Integer(ss[0]) + new Integer(ss[1]) ;
if(s2.equals("-"))
num = new Integer(ss[0]) - new Integer(ss[1]) ;
}else{
num = new Integer(s) ;
}
}
return num;
}