Hi all,
If your sandstone is red in colour? (like "old" (Devonian) and "new" (Triassic) red sandstones in the UK, or the red interior of Australia.) if it is red it will almost certainly be all right, and not contain carbonates. These rocks are red because all the soluble minerals have been washed out of them, just leaving the oxidised ferrous iron behind (like tropical laterite clays).
Nearly all forms of limestone are fairly pale in colour (Chalk or Bath stone for example). What the good doctor says about acids is also true, but if you have a rock where scraping the surface and applying strong HCl to it is needed to liberate the carbonates in aquarium terms it is, to all intents and purposes, inert. As an example Ireland is covered by Carboniferous limestone, a limestone that is both old and hard, and peat bogs can form right on top of it in the wet climate. Australia is a very old continent, with hard old rocks and therefore I would have no problem with using any hard old sandstone in soft water tanks.
What you have to remember is sandstones are exactly what they say they are "rocks made from sand". A parent rock (an igneous one like granite, or a limestone or another older sandstone) is reduced to sand grains and then that sand is then buried by geological processes and cemented together by heat and pressure deep underground. Only very hard limestones will form sand grains (normally the hardest mineral quartz is left), although shell fragments are a complicating factor.
There are 2 possible sources of carbonates, the original rock that was reduced to grains of sand was a hard (or shell limestone) and the "cement" that holds the rock grains together may be impregnated with calcite (you can think of the calcite like the tufa you get where lime rich "petrifying" springs come up in the Peak District, Yorkshire Dales, Mendips etc.)
Despite the mention of the true home of bitter beer, gypsums are largely irrelevant to us in the UK (in this case the gypsum is deep underground and in the same area that the Cheshire salt deposits were laid down under an arid tropical climate), but where the climate is fairly arid they may occur in the rocks.
cheers Darrel