Hello C# 006

"It's no use going back to yesterday, because I was a different person then" – Lewis Carroll (maybe)

Characters

In the computer every letter/character is mapped to a number. Sequence of characters are called string and may be represented in many ways (like this one). We've already used a implementation of list with the first number being the amount of elements and the following indexes containing the list content.

In C# is easy to get the number related to a character by enclosing it into single quotes. Just note that 'x' is not an int properly, but the system can cast it automatically to int when storing it.

Cast

Cast is about changing the type of the data, which changes how the data is manipulated. Casts may happen implicitly or may result in an error.

> 'c'
'c'
> (int)'c'
99
> (char)99
'c'
> int a = 99; // this is a variable declaration which sets the type of the variable explicitly
> a = 'b'
98
> a
98
> (char) a
'b'
> 'c' + 2
101
> (char) 'c' + 2 // casting, notice how it executes ((char) 'c') + 2
101
> (char)('c' + 2)
'e'
> char b = 99; // error!
(1,10): error CS0266: Cannot implicitly convert type 'int' to 'char'. An explicit conversion exists (are you missing a cast?)
> char b = (char)99; // so char to int casts automatically, int to char does not
> b
'c'
> b+10 // this is because chars do not express all the numbers ints can
109
> int.MaxValue
2147483647
> (int)char.MaxValue
65535
> b = b+10 //another error
(1,5): error CS0266: Cannot implicitly convert type 'int' to 'char'. An explicit conversion exists (are you missing a cast?)
> b = (int)b +10 // another error
(1,5): error CS0266: Cannot implicitly convert type 'int' to 'char'. An explicit conversion exists (are you missing a cast?)
> b = (char)((int)b +10) // ok
> b = (char)(b + 19999999) // should it work?
'\u2d6c'
> (int) b // Check modular arithmetic to learn more
11628

Our problem

We are going to solve the classical problem of balanced parenthesis:

A string consisted only of '(' and ')' is considered balanced if and only if for every '(' there is a subsequent ')' properly nested.
Balanced examples:

Unbalanced examples:

We solve it using the stack, each '(' results in a push to the stack and each ')' results in a pop, if the pop fails because the stack is empty we have a badly nested ')' and if the stack ends not empty we have extras '('. You do not need to worry why this works right now, but you may try to grasp how it works.

Lets organize our memory  before coding:

And here is the solution

> var m = new int[256];
> m[1] = 4; m[2] = '('; m[3] = '('; m[4] = ')'; m[5] = ')'; // write (())
> m[100] = 0; // initialize the stack
> m[99] = 0; // number to traverse the string
> while (m[99] < m[1])
{
m[99]++; // shorthand for m[99] = m[99] + 1 but returning the old value
// ++m[99] returns the new value;
if(m[1+m[99]] == '(') // we 'push'
m[100]++; // no need to store the value
else // it is the ')'
if(m[100] == 0) // nothing to pop means unbalanced string
m[99] = m[1] + 2; // just a way exit the loop and know we had an extra )
else
m[100]--;
}

> // if stack not empty or we had an extra `)`; note that || is the or operator
> if(m[100] != 0 || m[99] == (m[1] + 2))
m[0] = 0; else m[0] = 1; // ugly way to add the else in the REPL
> m[0]
1

[Try by yourself] Create a basic console application to make it easier to change the string tested and check the examples.

[Try by yourself] Try to extend the solution to handle more kinds of parenthesis like [] and {} (tip: this time you may need to push the value to the stack).

[Try by yourself] I did not tested the solution for other cases, mail me in case it does not work (^-^)!

Up Next

'Functions' and variables.


Go home.

☆Powered by Azure Blob