Алгоритмическая практика. Базовая алгоритмическая подготовка. Задачи 1, 2.
Primary tabs
Задача 1. Решите на Паскале и/или JS Задачку №10 Урока 17, про расчет выражений вида за один проход строки:
Входные данные Результат 5+2 7 1-2*5+2 -7 5*6+7-3*2+11 42 5*6+7-3*2*3+11 30
Решение
function calculator(str) { let prev = '', acc_sum = 0, acc_mul = 0, num = ''; for (let v of str) { if (!isNaN(v)) { num += v } else { num = +num; if (prev == '-') num = -num; prev == '*' ? acc_mul *= num : v == '*' ? acc_mul = num : acc_sum += num; if (v != '*') { acc_sum += acc_mul; acc_mul = 0; } prev = v; num = '' } } num = +num; prev == '*' ? acc_sum += acc_mul * num : prev == '+' ? acc_sum += num : acc_sum -= num; return `Ожидается: ${eval(str)} \nОтвет: ${acc_sum}` } let Y = '6+4*6*5-11*5+14*5*2+3+5-44*5'; console.log(calculator(Y));
Задача 2. Решите на Паскале и/или JS Задачку №8 Урока 20, про расчет выражений вида:
5*(3+4)-7*9+3*(2+(2-7))
с помощью рекурсии.
Решение
Вариант 1. Алгоритм поиска в глубину
function calc_recurse(str, i = 0) { let prev = '', acc_sum = 0, acc_mul = 0, num = ''; for (; i < str.length; i++) { if (!isNaN(str[i])) { num += str[i] } else { num = +num; if (str[i] == '(') [num, i] = calc_recurse(str, i + 1); if (prev == '-') num = -num; prev == '*' ? acc_mul *= num : str[i] == '*' ? acc_mul = num : acc_sum += num; if (str[i] != '*') { acc_sum += acc_mul; acc_mul = 0 } if (str[i] == ')') return [acc_sum, i + 1]; prev = str[i]; num = '' } } num = +num; prev == '*' ? acc_sum += acc_mul * num : prev == '+' ? acc_sum += num : acc_sum -= num; return `Ожидается: ${eval(str)} \nОтвет: ${acc_sum}` } let Y = '-(6*8+(4*6-11))*4-1*(5+1)+9-3*(-355)'; console.log(calc_recurse(Y));
Вариант 2. Алгоритм из интернета, без цикла, с двумя массивами-стеками чисел и знаков + добавлена проверка скобок.
function recursive(a, i = 0, num = [], z = []) { if (i < a.length) { if (!isNaN(a[i])) { num[num.length] = +a[i]; i += 1 } if (!z.length) { if (!num.length) num[0] = 0; z[0] = a[i]; i += 1 } else { if (z[z.length - 1] == '+' || z[z.length - 1] == '-') { if (a[i] != '*' && a[i] != '(') { z[z.length - 1] == '+' ? num[num.length - 2] += num[num.length - 1] : num[num.length - 2] -= num[num.length - 1]; num.length -= 1; z.length -= 1 } else { z[z.length] = a[i]; i += 1 } } else { if (z[z.length - 1] == '*') { if (a[i] != '(') { num[num.length - 2] *= num[num.length - 1]; num.length -= 1; z.length -= 1 } else { z[z.length] = a[i]; i += 1 } } else { if (a[i] == '-' && a[i - 1] == '(') num[num.length] = 0; a[i] == ')' ? z.length -= 1 : z[z.length] = a[i]; i += 1; if (i == a.length && z.length) i -= 1 // Чтобы не выходить за пределы массива } } } return recursive(a, i, num, z) } return num.length == 1 ? num[0] : z[0] == '+' ? num[0] + num[1] : // Либо return num[0], z[0] == '-' ? num[0] - num[1] : num[1] //если выходить за пределы массива } function isSolved(st, i = 0, a = []) { if (i < st.length) { if (st[i] == ')') { if (a[a.length - 1] == '(') { a.length -= 1 } else { return false } } if (st[i] == '(') a[a.length] = '('; return isSolved(st, i + 1, a) } return !a.length } function solution(value) { let arr = value.match(/[()+*-]|\d+/g); return isSolved(value) ? `Ожидается: ${eval(value)} \nОтвет: ${recursive(arr)}` : 'Нет решения' } let s='-5-(-1+6*5-4)*6*5+8*9*17+11*9*(0-14*5)*5*(2-(3*(5*4*8)))*(-2*3-5)-8+((4-9*6)-1-(-3*5)*(1-6))'; console.log(solution(s));
- Log in to post comments
- 533 reads
vedro-compota
Wed, 07/12/2023 - 20:06
Permalink
засчитано
засчитано
_____________
матфак вгу и остальная классика =)