Replcing line breaks with <p></p>?

I have a form which lets the user enter text and add this to the database.
When this text is pulled from mySQL database, I use the function 'nl2br' to convert \r\n to <br>.

So my html text comes out as

This is a paragraph<br><br>
This is another paragraph<br><br>


...but I really need it to come out as:

<p>This is a paragraph</p>
<p>This is another paragraph</p>


Does anyone have suggestions on how to do this ?

<?php
$str = str_replace("\n","</p><p>",$str);
echo '<p> ' . $str . ' </p>';
?>