-
Notifications
You must be signed in to change notification settings - Fork 0
/
4-postfix.js
129 lines (117 loc) · 3.04 KB
/
4-postfix.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/** [후위식 연산]
* 후위 연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요
* 만약 3*(5+2)-9를 후위연산식으로 표현하면 352+*9-로 표현되며 그 결과는 12입니다
*
* 조건:
* - 연산식의 길이는 최대 50을 넘지 않습니다
* - 식은 1~9의 숫자와 +, -, *, / 연산자로만 이루러집니다
* */
const PARENTHESIS = {
OPEN: '(',
CLOSE: ')',
};
const OPERATOR = {
PLUS: '+',
MINUS: '-',
MULTIPLY: '*',
DIVIDE: '/',
};
const getPostfixArr = (infixArr) => {
const postfixArr = [];
const stack = [];
const getPrecedence = function(operator) {
switch (operator) {
case OPERATOR.MULTIPLY:
case OPERATOR.DIVIDE:
return 3;
case OPERATOR.PLUS:
case OPERATOR.MINUS:
return 2;
case PARENTHESIS.OPEN:
case PARENTHESIS.CLOSE:
return 1;
default:
return 0;
}
}
infixArr.forEach(item => {
if (!isNaN(item)) {
postfixArr.push(item);
} else {
if (!stack.length) {
stack.push(item);
} else {
switch (item) {
case PARENTHESIS.OPEN:
stack.push(item);
break;
case PARENTHESIS.CLOSE:
let operator;
while (stack.length) {
operator = stack.pop();
if (operator === PARENTHESIS.OPEN) {
break;
} else {
postfixArr.push(operator);
}
}
break;
case OPERATOR.PLUS:
case OPERATOR.MINUS:
case OPERATOR.MULTIPLY:
case OPERATOR.DIVIDE:
const topOperator = stack[stack.length - 1];
if (getPrecedence(item) > getPrecedence(topOperator)) {
stack.push(item)
} else {
postfixArr.push(stack.pop());
stack.push(item);
}
break;
default:
break;
}
}
}
})
stack.forEach(item => {
postfixArr.push(item);
})
return postfixArr;
};
const calculatePostfix = (postfixArr) => {
const stack = [];
const calculate = {
[OPERATOR.PLUS]: (num1, num2) => num1 + num2,
[OPERATOR.MINUS]: (num1, num2) => num1 - num2,
[OPERATOR.MULTIPLY]: (num1, num2) => num1 * num2,
[OPERATOR.DIVIDE]: (num1, num2) => num1 / num2,
};
postfixArr.forEach(item => {
if (!isNaN(item)) {
stack.push(item);
} else {
const num2 = Number(stack.pop());
const num1 = Number(stack.pop());
stack.push(calculate[item](num1, num2));
}
})
return stack[0];
};
function test(str) {
if (str.length > 50) {
console.warn('최대 입력 글자수는 50개입니다');
return;
}
const infixArr = [...str];
const postfixArr = getPostfixArr(infixArr);
const result = calculatePostfix(postfixArr);
console.log(`postfix: ${postfixArr.join('')} / result: ${result}`);
return result;
};
// Execute Test
const exampleStrList = [
'5+2*3',
'3*(5+2)-9',
];
exampleStrList.forEach(exampleStr => test(exampleStr));