간단한 표현식 문자열이 있고 해당 표현식을 평가하기 위해 기본 계산기를 구현해야 한다고 가정합니다. 표현식 문자열은 여는 괄호와 닫는 괄호, 더하기 + 또는 빼기 기호 -, 음이 아닌 정수 및 공백을 포함할 수 있습니다. 표현식 문자열에는 음이 아닌 정수, +, -, *, / 연산자, 여는 괄호와 닫는 괄호, 공백만 포함됩니다. 정수 나누기는 0 쪽으로 잘려야 합니다.
따라서 입력이 "6-4 / 2"와 같으면 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
l1 :=0, l2 :=1
-
o1 :=1, o2 :=1
-
하나의 스택 정의
-
n :=s
의 크기 -
initialize i :=0의 경우, i
-
x :=s[i]
-
x>='0'이고 x <='9'이면 -
-
숫자 :=x - '0'
-
동안 (i + 1
='0' 및 s[i + 1] <='9'), 수행 - -
(i를 1씩 증가)
-
숫자 :=(숫자 * 10) + (s[i] - '0')
-
-
l2 :=(o2가 1과 같으면 l2 * num, 그렇지 않으면 l2 / num)
-
-
그렇지 않으면 x가 '('와 같을 때 -
-
st에 l1을 삽입하고 st에 o1을 삽입
-
st에 l2를 삽입하고 st에 o2를 삽입
-
l1 :=0, o2 :=1
-
o1 :=1, l2 :=1
-
-
그렇지 않으면 x가 ')'와 같을 때 -
-
온도 :=l1 + o1 * l2
-
o2 :=st의 최상위 요소
-
st
에서 요소 삭제 -
l2 :=st의 최상위 요소
-
st
에서 요소 삭제 -
o1 :=st의 최상위 요소
-
st
에서 요소 삭제 -
l1 :=st의 최상위 요소
-
st
에서 요소 삭제 -
l2 :=(o2가 1과 같으면 l2 * temp, 그렇지 않으면 l2 / temp)
-
-
그렇지 않으면 x가 '*'와 같거나 x가 '/'와 같을 때 -
-
o2 :=(x가 '*'와 같으면 1, 아니면 -1)
-
-
그렇지 않으면 x가 '+'와 같거나 x가 '-'와 같을 때 -
-
x가 '-'와 같고 (i가 0과 같거나 (i - 1>=0이고 s[i - 1]이 '(')와 같으면) -
-
o1 :=-1
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
l1 :=l1 + o1 * l2
-
o1 :=(x가 '+'와 같으면 1, 그렇지 않으면 -1)
-
l2 :=1, o2 :=1
-
-
-
l1 + o1 * l2를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int calculate(string s) {
lli l1 = 0;
lli l2 = 1;
lli o1 = 1;
lli o2 = 1;
stack<lli> st;
lli n = s.size();
for (lli i = 0; i < n; i++) {
char x = s[i];
if (x >= '0' && x <= '9') {
lli num = x - '0';
while (i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
num = (num * 10) + (s[i] - '0');
}
l2 = (o2 == 1) ? l2 * num : l2 / num;
}
else if (x == '(') {
st.push(l1);
st.push(o1);
st.push(l2);
st.push(o2);
l1 = 0;
o2 = 1;
o1 = 1;
l2 = 1;
}
else if (x == ')') {
lli temp = l1 + o1 * l2;
o2 = st.top();
st.pop();
l2 = st.top();
st.pop();
o1 = st.top();
st.pop();
l1 = st.top();
st.pop();
l2 = (o2 == 1) ? l2 * temp : l2 / temp;
}
else if (x == '*' || x == '/') {
o2 = (x == '*') ? 1 : -1;
}
else if (x == '+' || x == '-') {
if (x == '-' && (i == 0 || (i - 1 >= 0 && s[i - 1] == '('))) {
o1 = -1;
continue;
}
l1 += o1 * l2;
o1 = (x == '+') ? 1 : -1;
l2 = 1;
o2 = 1;
}
}
return l1 + o1 * l2;
}
};
main(){
Solution ob;
cout << (ob.calculate("(5+9*3)/8"));
} 입력
"(5+9*3)/8"
출력
4