当前位置: 动力学知识库 > 问答 > 编程问答 >

Switchbox routing with stack (java language)

问题描述:

I've been working on my college assignment about stacks in java, but I can't seem to find the help for this assignment. It's about switchbox routing and I'm required to use stack for this assignment. The assignment is due tomorrow, but there's no need to rush for answers since I'm only looking for the solutions and not the grades. Since the problem isn't written in english, I'm going to give short explanation.

The switchbox contains 4n pins, with n pins on each side of the box. The switchbox is routable only when none of the lines connecting a pair of pins intersect another. The input will be pairs of connected pin numbers.

A few possible solutions I've found but can't understand:

1. The problem can be solved with a similar algorithm as the one for the parentheses matching

2. Putting the pin numbers in stack and an array and compare them (this is the most confusing one)

My code so far (trying the second algorithm):

import java.util.Scanner;

import java.util.Stack;

public class Tester {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int cases=sc.nextInt();

for(int i=0;i<cases;i++){

int pin=sc.nextInt();

SwitchBox box=new SwitchBox(pin);

for(int j=0;j<pin*4;j++){

box.add(sc.nextInt());

}

boolean res=box.isRoutable();

if(res){

System.out.println("routable");

}

else{

System.out.println("not routable");

}

}

}

static class SwitchBox{

Stack<Integer> pins;

int[] pairs;

int[] comparator;

public SwitchBox(int pin){

this.pins=new Stack<Integer>();

this.pairs=new int[(pin*4)];

this.comparator=new int[this.pairs.length];

}

public boolean isRoutable(){

Stack<Integer> s=new Stack<Integer>();

for(int i=0;i<pairs.length;i++){

pairs[i]=pins.peek();

s.push(pins.pop());

}

for(int i=pairs.length-1;i>=0;i--){

if(pairs[i]!=s.pop()){

return true;

}

}

return false;

}

public void add(int pinNum){

if(pins.isEmpty()){

pins.push(pinNum);

}

else{

Stack<Integer> temp=new Stack<Integer>();

int top=(int)pins.peek();

while(top>pinNum){

temp.push(pins.pop());

if(pins.isEmpty()) top=pinNum;

else top=(int)pins.peek();

}

pins.push(pinNum);

while(!temp.isEmpty()){

pins.push(temp.pop());

}

}

}

}

}

网友答案:

In your add method else block is wrong. I was unable to understand what you try to do but you need to do next thing

public void add(int pinNum) {
    if (pins.isEmpty()) {
        pins.push(pinNum);
    } else {
        Integer last = pins.peek();
        if (last == pinNum) {
            pins.pop();
        } else {
            pins.push(pinNum);
        }
    }
}

After that isRoutable method just need to check pins stack. If it empty, then all fine. Else there are intersecting lines.

分享给朋友:
您可能感兴趣的文章:
随机阅读: