function Stack() {
this.dataSource = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear
}
function push(element) {
this.dataSource[this.top++] = element;
}
function pop(element) {
return this.dataSource[--this.top]
}
function peek() {
return this.dataSource[this.top - 1]
}
function clear() {
this.top = 0;
}
function length() {
return this.top
}
- 棿凹郏可以用來判斷一個算術表達式中的括號是否匹配射沟。編寫一個函數(shù)套蒂，該函數(shù)接受一個算術表達式作為參數(shù)，返回括號缺失的位置吟榴。下面是一個括號不匹配的算術表達式的例子：2.3 + 23 / 12 + (3.14159×0.24魁蒜。
function panduan(shizi) {
var s = new Stack();
var left = ['(', '{', '['];
var right = [')', '}', ']'];
for (let i = 0; i < shizi.length; i++) {
if (left.indexOf(shizi[i]) > -1) {
s.push(shizi[i])
} else if (right.indexOf(shizi[i]) > -1) {
var c = s.peek();
switch (shizi[i]) {
case '}':
if (c == '{') {
s.pop();
break;
}
return i + 1;
case ']':
if (c == '[') {
s.pop();
break;
}
return i + 1;
case ')':
if (c == '(') {
s.pop();
break;
}
return i + 1;
default: break;
}
}
}
if (s.length() > 0) {
return shizi.length+ 1;
}
return -1
}
console.log(panduan('2+3/1+(3*2')) //11
console.log(panduan('2+(3/1)+(3*2')) //13
2.使用兩個棧，一個用來存儲操作數(shù)吩翻，一個用來存儲操作符兜看，設計并實現(xiàn)一個js函數(shù)，該函數(shù)可以將中綴表達式轉換為后綴表達式狭瞎，然后利用棧對該表達式求值细移。
function infixToPostfix(exp) {
var operatorStack = new Stack();
var postfixExp = [];
exp.split('').forEach(function (char) {
if (isOperator(char)) {
// 比較優(yōu)先級
while (comparePriority(operatorStack.peek(), char)) {
var tmp = operatorStack.pop();
if (tmp !== '(' && tmp !== ')') {
postfixExp.push(tmp);
}
if (tmp === '(' && char === ')') { // 匹配到左括號的時候，結束循環(huán)熊锭。
break;
}
}
if (char !== ')') {
operatorStack.push(char);
}
} else {
postfixExp.push(char);
}
});
while (operatorStack.length()) {
postfixExp.push(operatorStack.pop());
}
return postfixExp.join('');
}
function computePostfix(exp) {
var numStack = new Stack();
exp.split('').forEach(function (char) {
if (char.trim()) {
if (!isOperator(char)) {
numStack.push(char);
} else {
var tmp = numStack.pop();
numStack.push(eval(numStack.pop() + char + tmp));
}
}
});
return numStack.pop();
}
var postfixExp = infixToPostfix('(8-2)/(3-1)*(9-6)');
var postfixExpValue = computePostfix(postfixExp);
console.log(postfixExp); // 82-31-/96-*
console.log(postfixExpValue); // 9
- 佩茲糖果盒弧轧，不改變其他顏色糖果將黃色糖果移出
// 1:紅 2：黃 3：白
var s = [1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 1, 1, 3, 3, 1, 2, 3, 1, 3, 2]
function yichusugger(arr) {
var s = new Stack();
for (let i = 0; i < arr.length; i++) {
s.push(arr[i])
}
var newArr = [];
while (s.length() > 0) {
var color = s.pop();
if (color != 2) {
newArr.push(color)
}
}
return newArr
}
console.log(yichusugger(s))
