深セン同城の速く走る筆記試験のテーマ3は4則の演算を実現します
66254 ワード
package com.cici. ;
import java.util.Stack;
class Node
{
public char cData; // data item (key)
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(cData);
System.out.print("} ");
}
} // end class Node
class Tree
{
public Node root; // first node of tree
public int size;
//-------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
//-------------------------------------------------------------
public Node find(char key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.cData != key) // while no match,
{
if(key < current.cData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
//-------------------------------------------------------------
public void insert(char c)
{
Node newNode = new Node(); // make new node
newNode.cData = c; // insert data
if(root==null) // no node in root
root = newNode;
else // root occupied
{
//make a new node which is stands for the new node
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
//parent node is the root node
parent = current;
//go left ?
if(check(c)){
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.leftChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
//-------------------------------------------------------------
public boolean delete(char key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.cData != key) // search for node
{
parent = current;
if(key < current.cData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
//-------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
//-------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print("
Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("
Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("
Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
//-------------------------------------------------------------
public void preOrder(Node localRoot)
{
if(localRoot != null)
{
preOrder(localRoot.leftChild);
System.out.print(localRoot.cData + " ");
preOrder(localRoot.rightChild);
}
}
//-------------------------------------------------------------
public Node inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.cData + " ");
inOrder(localRoot.rightChild);
}
return localRoot;
}
//-------------------------------------------------------------
public void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.cData + " ");
}
}
//check the whether a node is a signal
public static boolean check(Character ch){
if(ch.equals(new Character('+')) || ch.equals(new Character('-'))
|| ch.equals(new Character('*'))
|| ch.equals(new Character('\\') )
|| ch.equals(new Character('^')) )
{
return true;
}
return false;
}
public long calculate( ){
long result = 0;
result+=this.root.cData-48;
Node localRoot= root.leftChild;
while(localRoot!=null){
if(localRoot.cData=='+'){
if(localRoot.rightChild!=null){
result+=localRoot.rightChild.cData-48;
}
}
if(localRoot.cData=='-'){
if(localRoot.rightChild!=null){
result-=localRoot.rightChild.cData-48;
}
}
if(localRoot.cData=='/'){
if(localRoot.rightChild!=null){
result/=localRoot.rightChild.cData-48;
}
}
if(localRoot.cData=='*'){
if(localRoot.rightChild!=null){
result*=localRoot.rightChild.cData-48;
}
}
/*int m = 4;
int n = 2;
int result = 1;
for(int i=0;i<n;i++){
result*=m;
}
System.out.println(result);*/
if(localRoot.cData=='^'){
long temp = 1;
for(int i=0;i<localRoot.rightChild.cData-48;i++){
temp*=result;
}
result= temp;
}
localRoot= localRoot.leftChild;
}
return result;
}
//-------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.cData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
//-------------------------------------------------------------
} // end class Tree
public class TreeApp{
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert('2');
tree.insert('^');
tree.insert('3');
tree.insert('+');
tree.insert('1');
tree.insert('*');
tree.insert('2');
tree.displayTree();
long result = tree.calculate();
System.out.println("----"+result+"----");
}
}以上のコードは優先順位を考慮していません.以下のコードは4つの演算記号の有限レベルを考慮します.
しかし、正解は出力されなかった.calculate()の方法はまだ間違っているからです.これによって得られた結論はノードの木の構造を利用するのは複雑すぎる.なるべく避ける本人は暇な时間があればjdkのtreeを参考にします.
でもまだ難しいです.デバッグは何度も正しい結果を出力.今日はあきらめるつもりです.プログラムを修正できる達人がいるので、修正を見てほしいです.私は本当に変えたくない.
package com.cici. ;
import java.util.Stack;
class Node
{
public char cData; // data item (key)
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public Node(char cData){
this.cData = cData;
}
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(cData);
System.out.print("} ");
}
} // end class Node
class Tree
{
public Node root; // first node of tree
public int size;
//-------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
//-------------------------------------------------------------
public Node find(char key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.cData != key) // while no match,
{
if(key < current.cData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
//-------------------------------------------------------------
public void insert(char c)
{
Node newNode = new Node(c); // make new node
if(root==null&&!check(c)){
root = new Node(' ');
root.rightChild=newNode;
size++;
return;
} // no node in root
else if(root!=null&!check(root.cData)){
Node temp = root.rightChild;
root=new Node(c);
root.rightChild=temp;
size++;
return;
}
else // root occupied
{
//make a new node which is stands for the new node
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
//parent node is the root node
parent = current;
//go left ?
if(check(c)){
current = current.leftChild;
if(current.cData == ' ') // if end of the line,
{ // insert on left
newNode=new Node(c);
newNode.rightChild=current.rightChild;
parent.leftChild = newNode;
size++;
return;
}
else continue;
} // end if go left
else // or go right?
{
current = current.leftChild;
if(current == null) // if end of the line
{ // insert on right
newNode = new Node(' '); // make new node
newNode.rightChild=new Node(c);
parent.leftChild = newNode;
size++;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
//-------------------------------------------------------------
public boolean delete(char key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.cData != key) // search for node
{
parent = current;
if(key < current.cData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
//-------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
//-------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print("
Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("
Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("
Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
//-------------------------------------------------------------
public void preOrder(Node localRoot)
{
if(localRoot != null)
{
preOrder(localRoot.leftChild);
System.out.print(localRoot.cData + " ");
preOrder(localRoot.rightChild);
}
}
//-------------------------------------------------------------
public Node inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.cData + " ");
inOrder(localRoot.rightChild);
}
return localRoot;
}
//-------------------------------------------------------------
public void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.cData + " ");
}
}
//check the whether a node is a signal
public static boolean check(Character ch){
if(ch.equals(new Character('+')) || ch.equals(new Character('-'))
|| ch.equals(new Character('*'))
|| ch.equals(new Character('/') )
|| ch.equals(new Character('^')) )
{
return true;
}
return false;
}
public long calculate(){
Node current = this.root;
Node parent = this.root;
long result = 0;
//handle * / ^
while(current.cData!=' '){
int item1 = current.rightChild.cData-48;
int item2 = current.leftChild.rightChild.cData-48;
long temp = 1;
if(current!=null && current.cData=='*'){
result =item1*item2;
Node next = current.leftChild;
next.rightChild=new Node(((char) (result+48)));
// parent.cData=next.cData;
parent.leftChild = next;
current = next;
continue;
}if(current!=null && current.cData=='/'){
result =item1/item2;
Node next = current.leftChild;
next.rightChild=new Node(((char) (result+48)));
// parent.cData=next.cData;
parent.leftChild = next;
current = next;
continue;
}if(current!=null && current.cData=='^'){
for(int i=0;i<item2;i++){
temp*=result;
}
result = temp;
Node next = current.leftChild;
next.rightChild=new Node(((char) (result+48)));
// parent.cData=next.cData;
parent.leftChild = next;
current = next;
continue;
}
parent=current;
current = current.leftChild;
}
//handle + -
//parent = root;
root.leftChild =parent;
parent = root;
current = root;
while(current.leftChild!=null ){
result = 0;
int item1 = parent.rightChild.cData-48;
int item2 = parent.leftChild.rightChild.cData-48;
//long temp = 1;
if(parent.cData=='+'){
result +=item1+item2;
}if(parent.cData=='-'){
result +=item1-item2;
}
current = current.leftChild;
parent=current;
}
return result;
}
//-------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.cData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
//-------------------------------------------------------------
} // end class Tree
public class TreeApp{
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert('1');
tree.insert('+');
tree.insert('6');
tree.insert('/');//2+6/2*3^2+3
tree.insert('2');
tree.insert('*');
tree.insert('3');
tree.insert('^');
tree.insert('2');
tree.insert('+');
tree.insert('7');
tree.displayTree();
long result = tree.calculate();
System.out.println("----"+result+"----");
}
}