expression infix to postfix

대략적 스텝

1. str => []
2. infix => postfix
3. calculate postfix

주의할 점

• string을 "(100+100)" => ["(", "100", "+", "100", ")"]
  - 마지막 숫자 빼먹지 말기
• infix => postfix ["100", "100", "+"]
  • 부호는 oprStack에 , 숫자는 바로 postfix에
  • priority (3: ^, 2: */, 1: +-, 0: ...)
  • stack에서 빼서 postfix에 넣는 경우는 2가지
    1. previous priority가 current priority보다 크거나 같으면 previous를 먼저 pop한뒤 postfix에 넣어준다. (previous < current 일 때까지)
    2. ()가 닫힐때
  • (는 priority 상관없이 넣는다 -*(
• postfix 계산

문제

풀이

function getPriority(opr) {
  if (opr === "*" || opr === "/") return 2;
  else if (opr === "+" || opr === "-") return 1;
  else return 0;
}

function infixToPostfix(arr) {
  const oprStack = [];
  const postfix = [];

  for (const curr of arr) {
    // number
    if (!isNaN(Number(curr))) {
      postfix.push(curr);
    }
    // operator
    else {
      // 처음에 없거나, ( 이면 넣는다
      if (!oprStack.length || curr === "(") oprStack.push(curr);
      else {
        let previous = oprStack[oprStack.length - 1];
        // ) 면 ( 전까지를 postfix에 넣는다
        if (curr === ")") {
          while (previous !== "(") {
            // 주의
            postfix.push(oprStack.pop());
            previous = oprStack[oprStack.length - 1];
          }
          oprStack.pop(); // 남은 ( 도 빼준다
        }
        // (,) 以外的 operator
        else {
          // priority를 비교해서 prev < c 할때까지 pop한다
          while (getPriority(previous) >= getPriority(curr)) {
            postfix.push(oprStack.pop());
            previous = oprStack[oprStack.length - 1];
          }
          oprStack.push(curr);
        }
      }
    }
  }
  // 남은 부호들을 뒤에서부터 순서대로 postfix에 넣는다
  while (oprStack.length) {
    postfix.push(oprStack.pop());
  }

  return postfix;
}

// console.log(infixToPostfix("3*(4+1)")); // 341+*

function calcPostfix(postfix) {
  const resultStack = [];
  let n1 = null;
  let n2 = null;

  for (const p of postfix) {
    switch (p) {
      case "+":
        resultStack.push(resultStack.pop() + resultStack.pop());
        break;
      case "-":
        n2 = resultStack.pop();
        n1 = resultStack.pop();
        resultStack.push(n1 - n2);
        break;
      case "*":
        resultStack.push(resultStack.pop() * resultStack.pop());
        break;
      case "/":
        n2 = resultStack.pop();
        n1 = resultStack.pop();
        let divisionResult = Math.floor(n1 / n2);
        divisionResult = divisionResult > 0 ? divisionResult : 0; // 10 / -100 = 0
        resultStack.push(divisionResult);
        break;
      default:
        resultStack.push(Number(p));
        break;
    }
  }
  return resultStack[0];
}

// console.log(calcPostfix(["2", "1", "+", "3", "*"]));
// console.log(calcPostfix(["4", "13", "5", "/", "+"])); // 6
// console.log(
//   calcPostfix(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])
// ); //22

function solve(s) {
  // str => []
  // infix => postfix
  // calculate postfix

  // str => []
  let numStr = "";
  let newArr = [];
  for (const e of s) {
    if (isNaN(Number(e))) {
      if (numStr.length) {
        newArr.push(numStr);
        numStr = "";
      }
      newArr.push(e);
    } else {
      numStr += e;
    }
  }
  numStr && newArr.push(numStr); // 添加 最后numStr ["100", "+"]

  // infix => postfix
  const postfix = infixToPostfix(newArr);
  // calculate postfix
  return calcPostfix(postfix);
}

console.log(solve("1+2")); //  ["1", "2", "+"], 3
console.log(solve("(2*(3-4))*5")); // ["2", "3", "4", "-", "*", "5", "*"], -10
console.log(solve("3+2*3*4-1")); //  ["3", "2", "3", "*", "4", "*", "+", "1", "-"], 26
console.log(solve("100+100")); //  ["100", "100", "+"], 200
console.log(solve("(3+4)*(5+(2-3))")); // ["3", "4", "+", "5", "2", "3", "-", "+", "*"], 28

2nd

function toArrS(s) {
  const arrS = [];
  let numStr = "";
  // to array
  for (const i of s) {
    if (isNaN(Number(i))) {
      if (numStr !== "") {
        arrS.push(Number(numStr));
        numStr = "";
      }
      arrS.push(i);
    } else {
      numStr += i;
    }
  }
  if (numStr) arrS.push(Number(numStr));
  return arrS;
}

function getPriority(symbol) {
  if (symbol === "*" || symbol === "/") return 2;
  else if (symbol === "+" || symbol === "-") return 1;
  else return 0;
}

function toPostfix(s) {
  const expStack = [];
  const symbolStack = [];
  // const i of s?
  //  arr.length === 0 arr === []
  for (const curr of s) {
    if (!isNaN(curr)) {
      expStack.push(curr);
    } else {
      if (symbolStack.length === 0 || curr === "(") {
        symbolStack.push(curr);
      } else {
        let prevSymbol = symbolStack[symbolStack.length - 1];
        if (curr === ")") {
          while (prevSymbol !== "(") {
            expStack.push(symbolStack.pop());
            prevSymbol = symbolStack[symbolStack.length - 1];
          }
          symbolStack.pop(); // (
        } else {
          // if (getPriority(prevSymbol) < getPriority(curr)) {
          //   symbolStack.push(curr);
          // }
          // loop
          while (getPriority(prevSymbol) >= getPriority(curr)) {
            expStack.push(symbolStack.pop());
            // symbolStack.push(curr);
            prevSymbol = symbolStack[symbolStack.length - 1];
          }
          symbolStack.push(curr);
        }
      }
    }
  }
  if (symbolStack.length !== 0) {
    while (symbolStack.length !== 0) {
      expStack.push(symbolStack.pop());
    }
  }
  return expStack;
}

function calcPostfix(s) {
  const stack = [];
  let num1 = null;
  let num2 = null;

  for (const e of s) {
    switch (e) {
      case "+":
        stack.push(stack.pop() + stack.pop());
        break;
      case "-":
        num1 = stack.pop();
        num2 = stack.pop();
        stack.push(num2 - num1);
        break;
      case "*":
        stack.push(stack.pop() * stack.pop());
        break;
      case "/":
        num1 = stack.pop();
        num2 = stack.pop();
        const result = Math.abs(Math.floor(num2 / num1));
        stack.push(result);
        break;
      default:
        stack.push(e);
    }
  }
  return stack[0];
}

function solve(s) {
  const postfix = toPostfix(toArrS(s));
  return calcPostfix(postfix);
}