[스택/큐2] 기능개발, 주식가격, 계산기

기능개발

조건에 맞는 값들을 queue에 쌓아두고

while문을 이용하여 모두 제거하는 식의 문제이다.

function solution(progresses, speeds) {
    var answer = [];
    let counter = 0;
    while(progresses.length) {
        for(let i = 0; i<progresses.length; i++){
            progresses[i] += + speeds[i]
        }
        while(progresses[0] >= 100){
            progresses.shift();
            speeds.shift();
            counter++
        }
        if(counter) {
            answer.push(counter);
            counter=0;
        }
    }
    return answer;
}

주식가격

설명 없음

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer;
    for(int i =0; i<prices.size(); i++) {
        int count = 0;
        for(int j=i; j<prices.size(); j++) {
            if(prices[i] > prices[j]){
                answer.push_back(count);
                break;
            }
            if(j == prices.size()-1) {
                answer.push_back(count);
                break;
            }
            count++;
        }
    }
    return answer;
}

계산기

문자열로 입력된 수식을 연산하고 결과값을 출력하는 코드를 작성하시오. (eval 사용 금지)

input: "1+7*(15-1)/2"

output: 50

 

스택의 난이도 있는 문제이다.

스택의 어려움은 조건이 많기 때문인데 사칙연산은 순서에 있어서 많은 조건이 있기 때문이다.

 

계산 방법은

현재의 중위 표기법으로 된 식을 후위 표기법으로 바꾼 후 계산한다.

그렇기 때문에 크게 두가지 코드로 나누었다.

const question = "1+7*(15-1)/2"
const stack = []
const output = []
function postfix(question) {
    const arr = []
    let tempNum = ""
    for(let index in question) {
        
        let nowNumCheck = question[index].match(/[0-9]/)
        
        if(arr.length) {
            let lastNumCheck = arr[arr.length-1].match(/[0-9]/)
            if(lastNumCheck && !nowNumCheck) {
                arr.push(question[index])
            }else if(!lastNumCheck && nowNumCheck){
                arr.push(question[index])
            }else if(!lastNumCheck && !nowNumCheck) {
                arr.push(question[index])
            }else{
                tempNum = arr.pop() + question[index]
                arr.push(tempNum)
                    
            }
        }else {
            arr.push(question[index])
 
        }
    }
    
    for(value of arr) {
        if(!value.match(/[0-9]/)) {
            if(!stack.length) {
                stack.push(value)
            }else{
                if(value == "(") {
                    stack.push(value);
                }
                if(value == ")") {
                    while(stack.length) {
                        let target = stack.pop()
                        if(target != "(") {
                            output.push(target)
                        }else{
                            break;
                        }
                        
                    }
                    if(output[output.length-1] == "+" || output[output.length-1] == "-") {
                        while(true){
                            if(stack[stack.length-1] == "*" || stack[stack.length-1] == "/") {
                                output.push(stack.pop());
                            }else{
                                break;
                            }
                        }
                    }
                }
                if(stack.indexOf("(") >= 0) {
                    if(value != "(")
                        stack.push(value);
                }else{
                    if(value == "+" || value == "-") {
                        if(
                            stack[0] == "*" ||
                            stack[0] == "/" || 
                            stack[0] == "+" || 
                            stack[0] == "–" ) {
                            for(let i =0; i<stack.length; i++) {
                                output.push(stack.pop())
                            }
                            stack.push(value);
                        }
                    }
                    if(value == "*" || value == "/") {
                        if(stack[0] == "*" || stack[0] == "/") {
                            output.push(stack.pop())
                            stack.push(value);
                        }else if(stack[0] == "+" || stack[0] == "-") {
                            stack.push(value);
                        }
                    }
                }
                }
        }else{
            output.push(value)
        }
    }
    while(stack.length) {
        output.push(stack.pop());
    }
}
 
postfix(question)

위 코드는 후위표기식을 작성하는 코드이다.

후위 표기식 조건은

1. 현재 타겟이 ( 일 경우에는

1-1. 타겟이 ) 이전까지의 모든 연산자를 스택에 입력한다.

1-2 타겟이 ) 일 경우 괄호안의 모든 연산자를 pop 하여 후위표기식에 입력한다.

 

2. 현재타겟이 (가 아닐 경우는

2-1. + 혹은 - 가 타겟 일떄

2-1-1. 만약 이전 값이 + - * / 일 경우 스택에 담겨진 모든 연산자를 pop하여 후위표기식에 넣는다.

2-2 * 혹은 -가 타겟일 때

2-2-1. 스택의 top이 * 혹은 / 라면 스택의 모든 * 와 / 를 pop하여 후위표기식에 넣는다.

2-2-2 스택의 top이 + 혹은 - 라면 스택에 해당 타겟을 push한다.

function calculator(output){
    const outputArr = output
    for(value of outputArr) {
        if(value.match(/[0-9]/)) {
            calStack.push(value)
        }else{
            let a = Number(calStack.pop())
            let b = Number(calStack.pop())
            if(value=="+") calStack.push(b + a)
            if(value == "-") calStack.push(b - a)
            if(value == "*") calStack.push(b * a)
            if(value == "/") Math.round(calStack.push(b / a))
        }
    }
    return calStack[0]
}