/* ----------------------------------------------------
数值转换
----------------------------------------------------- */
var Stack = require("ss-stack")
// 封装十进制转二进制的函数
function dec2bin(decNumer) {
// 定义变量
var stack = new Stack()
var remainder;
// 循环除法
while (decNumer > 0) {
remainder = decNumer % 2;
decNumer = Math.floor(decNumer / 2);
stack.push(remainder);
}
// 将数据取出
var binayriStrng = ""
while (!stack.isEmpty()) {
binayriStrng += stack.pop();
}
return binayriStrng;
}
console.log(dec2bin(10))
console.log(dec2bin(233))
console.log(dec2bin(1000))
/* ----------------------------------------------------
括号匹配问题
----------------------------------------------------- */
var Stack = require("ss-stack");
function validBraces(braces){
let leftBraReg = /[\(\{\[]/,
// 栈
rightBracket
braces = braces.split('')
let stack = new Stack();
for(let bracket of braces) {
if(leftBraReg.test(bracket)) {
stack.push(bracket)
}
else {
switch (bracket) {
case ')':
rightBracket = stack.pop()
if(rightBracket !=='(') {
return false
}
break
case ']':
rightBracket = stack.pop()
if(rightBracket !=='[') {
return false
}
break
case '}':
rightBracket = stack.pop()
if(rightBracket !=='{') {
return false
}
break
}
}
}
return stack.length === 0 ? true : false
}
function validStr(str){
console.log(`string ${str} valid result:${validBraces(str)}`);
}
validStr('123') // true
validStr(' ') // true
validStr('') //true
validStr('(') // false
validStr('{') // false
validStr('[') // false
validStr(')') // false
validStr('}') // false
validStr(']') // false
validStr('([{})]') // false
validStr('()') // true
validStr('{}') // true
validStr('[]') // true
validStr('()') // true
validStr('{}()') // true
validStr('[]()') // true
validStr('{([])}') // true
validStr('([{}])') // true
validStr('[({})]') // true
validStr('[1,2,3,4]') // true
validStr("(){}[]") // true
validStr("(}") // false
validStr("[(])") // false
validStr("([{}])") // true
/* ----------------------------------------------------
汉诺塔题解
----------------------------------------------------- */
var Stack = require("ss-stack");
var towerOfHanoi = function(n, from, help, to) {
if (n > 0) {
towerOfHanoi(n-1, from, to, help);
to.push(from.pop());
console.log('----------------');
console.log(`from: ${from.stack.toArray()}`);
console.log(`help: ${help.stack.toArray()}`);
console.log(`to: ${to.stack.toArray()}`);
towerOfHanoi(n-1, help, from, to);
}
}
var a = new Stack(),
b = new Stack(),
c = new Stack(),
n = 4;
for(let i = n; i > 0; i--) {
a.push(i);
}
// test
towerOfHanoi(a.length, a, b, c);
/* ----------------------------------------------------
调度场算法，将中缀转换过程后缀表达式
----------------------------------------------------- */
var Stack = require("ss-stack");
// 操作符优先级列表
var PRI_LEFT = 99;
var PRI_RIGHT = 100;
var PRI_TOKEN_MAP = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': PRI_LEFT,
')': PRI_RIGHT,
};
// 将中序转换成
function infixToPostfix(expression){
expression = expression.replace(/\s*/g,""); // 去除所有空白字符
var opStack = new Stack();
var str = '';
// 符号栈操作
function calcToken(){
str += opStack.pop();
}
for(let token of expression){
var tokenPri = PRI_TOKEN_MAP[token] || 0;
var peekTokenPri = opStack.peek && PRI_TOKEN_MAP[opStack.peek] || 0;
// console.log(opStack.stack.toArray());
// 首先判断是否操作符
if(tokenPri){
// 情况 1： 栈顶不是左括号；入栈符号不是右括号
// 循环判断当前栈顶符号，且优先级高于或等于将要入栈的元素，且栈顶不是左括号
while(opStack.peek && PRI_TOKEN_MAP[opStack.peek] !== PRI_LEFT && tokenPri !== PRI_RIGHT && peekTokenPri >= tokenPri) {
calcToken();
}
// 情况2：右括号准备入栈，
if(tokenPri === PRI_RIGHT){
// 将符号栈中元素依次弹出，则需要弹栈一直到左括号
while(PRI_TOKEN_MAP[opStack.peek] !== PRI_LEFT){
calcToken();
}
opStack.pop(); // 将左括号弹出，不放在数字栈里
} else {
// 将当前符号元素入栈
opStack.push(token);
}
} else { // 不是操作符就直接拼接在字符串上
str += token;
}
}
// 将符号栈中剩余的元素依次弹出
while(opStack.peek){
calcToken();
}
return str;
}
console.log(infixToPostfix('1+2*3+4')); // "123*+4+"
console.log(infixToPostfix('1 + 2 * (4 + 5 - 6) ')); // "1 2 4 5 + 6 - * +"
console.log(infixToPostfix('1 + 2 * (3 + (4 + 5 - 6) * 2)')); // "1 2 3 4 5 + 6 - 2 * + * +"
console.log(infixToPostfix('a + b * c + ( d * e + f ) * g')); // "a b c * + d e * f + g * +"
/* ----------------------------------------------------
调度场算法，直接计算算术表达式
----------------------------------------------------- */
var Stack = require("ss-stack");
// 操作符优先级列表
var PRI_LEFT = 99;
var PRI_RIGHT = 100;
var PRI_TOKEN_MAP = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'(': PRI_LEFT,
')': PRI_RIGHT,
};
var FUNC_TOKEN_MAP = {
'+': function(a, b){return Number(a)+Number(b);},
'-': function(a, b){return Number(a)-Number(b);},
'*': function(a, b){return Number(a)*Number(b);},
'/': function(a, b){return Number(a)/Number(b);}
}
// 计算算术表达式
function calc(expression){
expression = expression.replace(/\s*/g,""); // 去除所有空白字符
var opStack = new Stack();
var numStack = new Stack();
// 符号栈操作
function calcToken(){
var b = numStack.pop();
var a = numStack.pop();
numStack.push(FUNC_TOKEN_MAP[opStack.pop()](a, b));
}
for(let token of expression){
var tokenPri = PRI_TOKEN_MAP[token] || 0;
var peekTokenPri = opStack.peek && PRI_TOKEN_MAP[opStack.peek] || 0;
// console.log(numStack.stack.toArray());
// 首先判断是否操作符
if(tokenPri){
// 情况 1： 栈顶不是左括号；入栈符号不是右括号
// 循环判断当前栈顶符号，且优先级高于或等于将要入栈的元素，且栈顶不是左括号
while(opStack.peek && PRI_TOKEN_MAP[opStack.peek] !== PRI_LEFT && tokenPri !== PRI_RIGHT && peekTokenPri >= tokenPri) {
calcToken();
}
// 情况2：右括号准备入栈，
if(tokenPri === PRI_RIGHT){
// 将符号栈中元素依次弹出，则需要弹栈一直到左括号
while(PRI_TOKEN_MAP[opStack.peek] !== PRI_LEFT){
calcToken();
}
opStack.pop(); // 将左括号弹出，不放在数字栈里
} else {
// 将当前符号元素入栈
opStack.push(token);
}
} else { // 不是操作符就直接拼接在字符串上
numStack.push(token);
}
}
// 将符号栈中剩余的元素依次弹出
while(opStack.peek){
calcToken();
}
return numStack.pop();
}
console.log(calc('1+2*3+4')); // "11"
console.log(calc('1 + 2 * (4 + 5 - 6) ')); // "7"
console.log(calc('1 + 2 * (3 + (4 + 5 - 6) * 2)')); // "19"
no comments
sign in to comment