Data structures and algorithms n3 - Essay Example

Now the first character “6” is read. Since “6” is a numeral, it is added to the output string. The next character “/” is read. Since “/” is an operator, it is pushed into the stack. The next character is “3”. Since “3” is a numeral, it is appended to the output string. The next character after “3” is “+”. Since “+” has a lower precedence than “/”, “/” is popped off the stack and appended to the output string; while “+” pushed into the stack. The next character is “2”.

Since it is a numeral, it is appended to the output string. The next character read is “*”. “*” has a higher precedence than “+”; therefore, “*” is pushed into the stack. The next character is “+”. Since left parenthesis is present on top of the stack, “+” operator is pushed into the stack. The next character after “+” is “1”, which is a numeral. It is appended to the output string. The next character that is encountered is a “)”. Therefore, all the elements in the stack are popped off until a “(” encountered; and those elements are appended to the output string.

The left parenthesis is popped off, but it is not appended to the output string. In our case, the “+” operator is appended to the output string. The next character to be read is “–”. Since “–” has a lower precedence than both “*” and “+”, they are popped off the stack and appended to the output string; while “–” is pushed into the stack. The next character that is encountered is “8”. It is appended to the output string. Next character after “8” is “/”.

Since “/” has a higher precedence over “–”, it is pushed into the stack. The next character that is encountered is “2”. It is a numeral; therefore, it is appended to the output string. We reach the end of the sample expression, as there is no character after “2”. Therefore, all the elements in the stack are popped off