2009 November | Polymath Programmer

Upgraded: Reverse Polish Notation with C#

November 5, 2009 By Vincent

I wrote a reverse polish notation tutorial for Dream In Code almost 2 years ago (wow that’s a long time ago!). The code only parsed for PI, E, numbers, the basic operators (plus, minus, multiply, divide), and the 3 basic trigonometric functions sine, cosine and tangent.

I’ve added more functions to it, and you can download the class here: ReversePolishNotation.cs

You can use the source code in a personal or commercial project. The disclaimer is that it’s given as is, and you’re ultimately responsible for what goes on in your project. Attribution to me (Vincent Tan) or a link to this blog is appreciated, but not necessary. Just do something awesome with it!

The new functions are

Absolute function
Arc sine (asin, inverse sine function)
Arc cosine (acos, inverse cosine function)
Arc tangent (atan, inverse tangent function)
Hyperbolic sine (sinh)
Hyperbolic cosine (cosh)
Hyperbolic tangent (tanh)
Square root function
Sign function

All in all, not very much added. But I’m using regular expressions to parse the input, so the more functions I support, the more complex the regular expression becomes. For example, I have to tell “sin”, “asin” and “sinh” apart. It’s harder because “sin” is a subset of “asin” and “sinh”.

Don’t get it? What if the input is “sing 1″? The parser should output 2 tokens, “sing” and “1″. It shouldn’t output “sin”, “g” and “1″ (or “sin” and “g 1″, or whatever weird case that shouldn’t happen).

Anyway, I haven’t been to Dream In Code for a while now… and someone’s commented that the regular expression for detecting the unary minus should be changed. This was the original code (broken up for legibility):

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+MINUS",
"${number} -");

This was what that person suggested:

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+\)\s+MINUS\s+\(",
"${number} ) - (");

If I understand it correctly, he (or she) wants to catch the situation where the input has something like this:
( 5 ) – ( 3 )

I checked, and my original parsing would indeed fail. I do think he overparsed (I made that word up) though. He made the assumption that the next number is also encapsulated in a round bracket. It doesn’t have to. My code will fail for this too:
( 5 ) – 3

The error was in the right round bracket, so the corrected code is

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+(?<bracket>[)]?)\s+MINUS",
"${number} ${bracket} -");

Basically, I checked for the existence of the round bracket. Let me take it out for you to see it better:

(?<bracket>[)]?)\s+

Anyway, I’m putting the upgraded RPN code here because I’m going to shut down the site where I put it. I made a playground site called Ragnarok Code (now defunct). After months, I still only have the RPN code up.

Let me just say that writing articles is hard, and takes a non-trivial amount of time. So that site’s been stagnating, which ironically is the very thing I wanted my coding skills to not be. *sigh*

So have a play with an implementation of RPN while it’s still up.

P.S. I checked that person’s profile on Dream In Code. Seems like the only thing he did was comment on my tutorial. Wow, it must have bugged him really bad for him to register an account just so he could comment on my tutorial. After about 2 months, there’s no more activity from him. Maybe he got tired of waiting for a reply from me… oops…

Why are signals from passive optical networks split into 32?

November 2, 2009 By Vincent

World map information

I attended a course on fibre technology recently. The presenter was Dr. Jeffrey Bannister from Orbitage.

He was talking about fibre optics being a relatively old technology, and is now being used as a means of transporting the vast amounts of information that’s the Internet. Remember the earthquakes near Taiwan, which halted Internet traffic in Asia?

There’s an interesting point he made, that there are only 4 of these hair-thin optical fibres supporting the Asian Internet traffic. And if I remember correctly, these optical fibres run in between Vietnam and Philippines, to Taiwan, and to Japan. I can’t find any reference on the number of fibres used, but 4 seems incredulous. I mean, it takes a lot of money, time and effort to set those submarine cables. It makes sense to use more, since optical fibres are cheap (as cheap as fishing lines, so says Dr Bannister). Maybe there are dark fibres.

Another interesting point is that optical fibres do not rely on electricity to convey information. Shine a light at one end of a fibre, and it’s interpreted as a “1″ at the other end. No light means a “0″. Voila! Zeroes and ones for digital use. Using a physics property called Brewster’s angle, light can be transmitted for long distances with little loss of energy or result in data corruption (light keeps bouncing around along the optical fibre).

A third interesting point is that the light used in transmitting our Internet data is not visible at all! It’s actually infrared light, because it has the best result for the single-mode optical fibres used.

A fourth interesting point is that upstream and downstream data use the same optical fibre. It’s accomplished by using different wavelengths of infrared light, using a technique called wavelength-division multiplexing.

So where do passive optical networks come in, and what are they? If I understand it correctly, it’s an architecture for housing splitters, and

Each splitter typically splits the signal from a single fiber into 16, 32, or 64 fibers, depending on the manufacturer, and several splitters can be aggregated in a single cabinet.

Remember the data travelling along just 4 optical fibres mentioned before? There are many endpoints for that data, so somewhere along the line, the data have to be split up. That’s where the splitters come in.

By now, your coder senses should be tingling. Let me highlight the source of the tingling:

single fiber into 16, 32, or 64 fibers

16? 32? 64? They look familiar…

In his talk, Dr Bannister mentioned that splitters split the signals into 32 or 64. Now if he mentioned only “32″, I might have waved it off. But he mentioned “64″ in the same breath too, and that’s what triggered my coder senses.

And in case you haven’t caught on,
16 = 2^4
32 = 2^5
64 = 2^6

So after his talk, I went up to ask him about this. At first, he misunderstood my question, and explained more on how the splitting was done.

My question was actually something else. Fibre optics do not need electricity to transmit data. The splitters do not need electricity to split signals. Basically everything is analog. Why is the binary concept, the basis of digital, used in the number of splits?

His answer was actually very simple. It’s easy to calculate the efficiency. (Or light energy. Or wavelength.) Splitting a signal into 2 means it’s a simple 50% divide.

He thought about it, and said the engineers could probably split signals into 10 or powers of 10. But splitting in powers of 2 is easy for the math.

Frankly speaking, I didn’t expect such a simple and logical answer. I was actually stunned for a few seconds.

Does that make you feel computers have a completely efficient understanding of the world?

[Update: Commenter John Bartell has more information on splitters and passive optical networks.]

[image by ktsimage]