/*
 * 实现一个Stack类（模拟数据结构里的栈），包括如下的方法
 * push元素入栈
 * pop 元素出栈并且删除栈顶元素
 * peek 元素出栈但是不删除栈顶元素
 * clear 清空栈
 * 
 * author ubuntuvim
 * website http://ibeginner.sinaapp.com
 */
function Stack() {
	this.dataStore = [];  //保存栈的元素
	this.top = 0;  //记录栈顶位置，会随着压栈、出栈而改变
	this.push = push;
	this.pop = pop;
	this.peek = peek;
	this.clear = clear;
	this.length = length;
}

/**
 * 压栈
 * @param e 压入栈的元素
 */
function push(e) {
	this.dataStore[this.top++] = e;  //  注意 ++ 的位置，先把元素入栈到top当前位置再增1
}

/**
 * 出栈
 * @return e 出栈的元素，并修改栈顶位置，
 */
function pop() {
	return this.dataStore[--this.top];  //  注意测试 -- 的位置
}

/**
 * 出栈
 * @return e 出栈的元素，不修改栈顶位置，如果对一个空栈调用 peek() 方法,结果为 undefined
 */
function peek() {
	return this.dataStore[this.top-1];  //  元素从0开始 this.top-1 正好是栈顶元素
}

/**
 * 获取栈的元素个数
 * @return 
 */
function length() {
	return this.top;  //栈顶位置即为栈的元素个数
}

/**
 * 清空栈
 */
function clear() {
	delete this.dataStore;
	this.dataStore = [];
	this.top = 0;
}

// 测试
var s = new Stack();
s.push("hello world");
s.push("ubuntuvim");
s.push("nba");
s.push("bill gates");

print("The stack length is " + s.length());
print("The top element is " + s.pop())
print("The stack length is " + s.length());
print("The top element is " + s.peek() + " (peek)");

s.push("push a new element");
print("The top element is " + s.peek() + " (peek)");
s.clear();
print("Empty after, the stask lenght is " + s.length());
print("Empty after, the top element is " + s.pop() + " pop");  //undefined
print("Empty after, the top element is " + s.peek() + " peek");  // undefined
s.push("Cynthia");

print("the top element is " + s.pop() + " pop");  //Cynthia


 // 使用栈将数字转换为二进制和八进制数。
function mulBase(num, base) {
	var s = new Stack();
	do {
		s.push(num % base);
		num = Math.floor(num /= base);
	} while (num > 0);
	var cv = "";
	while (s.length() > 0) {
		cv += s.pop();
	}

	return cv;
}

var num = 2783;
var base = 2;
var result = mulBase(num, base);
print("the " + num + " converted to base " + base + " is " + result);

/*
栈可以用来判断一个算术表达式中的括号是否匹配。
编写一个函数,该函数接受一个算 术表达式作为参数,返回括号缺失的位置。
下面是一个括号不匹配的算术表达式的例 子:2.3 + 23 / 12 + (3.14159×0.24。
*/
function checkBracket(regExpStr) {
	var stack = new Stack();
	for (var i = regExpStr.length - 1; i >= 0; i--) {
		// print("regExpStr[i] = " + regExpStr[i]);  //得到单个字符串
		if ('(' == regExpStr[i]) {
			stack.push(regExpStr[i]);
		} else if (')' == regExpStr[i]) {
			stack.pop();
		} if ('[' == regExpStr[i]) {
			stack.push(regExpStr[i]);
		} else if (']' == regExpStr[i]) {
			stack.pop();
		}

	}

	if (0 == stack.length()) {
		print("表达式括号匹配。");
	} else {
		print("表达式括号不匹配。");
	}
}

var s = "2.3+23/12+(3.14159×0.24)";
checkBracket(s);

var s2 = "33*23(1+3)+3230/3 - 323%(33";
checkBracket(s2);