Show Different Custom Menu on Different Category Pages

I have been using in_category function to display a set of menu on the sidebar. However, a much better way would be to show this menu on the top, as a navigation menu — in the form of custom menus.

Question:

I already have a custom menu, but is there a way I could replace this custom menu with another one whenever a reader visits a post from a particular category?

Example:

On homepage, this is the menu:

Home | Cat | Dog

On a post tagged with CAT category, this is the menu:

Home | Cat 1 | Cat 2

From my understanding, this is the current code:

if ( function_exists('wp_nav_menu') ) {
add_theme_support( 'nav-menus' );
register_nav_menus( array( 'primary-menu' => __( 'Primary Menu', 'woothemes' ) )    );
register_nav_menus( array( 'top-menu' => __( 'Top Menu', 'woothemes' ) ) );
}

And…

<?php
if ( function_exists( 'has_nav_menu' ) && has_nav_menu( 'primary-menu' ) ) {
    echo '<h3>' . woo_get_menu_name( 'primary-menu' ) . '</h3>';
    wp_nav_menu( array( 'sort_column' => 'menu_order', 'container' => 'ul', 'menu_id' => 'main-nav', 'menu_class' => 'nav fl', 'theme_location' => 'primary-menu' ) );
} else {
?>
    <ul id="main-nav" class="nav fl">
        <?php
        if ( get_option( 'woo_custom_nav_menu' ) == 'true' ) {
            if ( function_exists( 'woo_custom_navigation_output' ) ) { woo_custom_navigation_output( 'name=Woo Menu 1' ); }
        } else { ?>

            <?php if ( is_page() ) { $highlight = 'page_item'; } else { $highlight = 'page_item current_page_item'; } ?>
            <li class="<?php echo esc_attr( $highlight ); ?>"><a href="<?php echo esc_url( home_url( '/' ) ); ?>"><?php _e( 'Home', 'woothemes' ); ?></a></li>
            <?php wp_list_pages( 'sort_column=menu_order&depth=6&title_li=&exclude=' ); ?>
        <?php } ?>
    </ul><!-- /#nav -->
<?php } ?>
</section><!-- /.menus -->