sm 기술 블로그
[알고리즘] 문자열 계산기(스택 없이) 본문
스택없는 계산기
먼저 설명에 앞서 모든 기능을 완벽하게 구현할 것은 아니다.
따라서 알고리즘을 보고 각자 기호에 맞게 집어 넣으면 될 것 이다.
스택 방법이 더 쉬우며 스택방법은 완벽히 구현이 완료 되었으므로 스택을 보고 싶다면 클릭
String s1 = (1+(10+5)* 4) 을 계산해 보자
1. 괄호 제거
먼저 괄호가 있는 부분을 찾아야 한다.
괄호에 다음과 같은 규칙을 생각해야한다.
- 앞에서 부터 ")"가 첫번째로 나온 부분이 제일 먼저 계산해야 하는 부분이다.
- 뒤에서 부터 "("가 첫번째로 나온 부분이 제일 먼저 계산해야 하는 부분이다.
먼저 공백이 있으면 안되니 공백을 제거해주자
s1 = s1.replace(" ", "");
그 다음 먼저 계산해야하는 괄호를 찾아 s2에 저장하고, 그 부분에서 괄호를 뺀 부분을 s3에 저장한다.
String s2 = s1.substring(s1.lastIndexOf('('), s1.indexOf(')')+1);
String s3 = s1.substring(s1.lastIndexOf('(')+1, s1.indexOf(')'));
괄호가 있는 부분은 나중에 계산값을 replace를 통해 s1을 변환 해 줄거다.
괄호가 없는 부분은 계산을 위해 사용할 것이다.
다시말해 1번(괄호제거) 과정을 통해서 (1+(10+5)* 4) => (1+15*4) 로 만들어 줄거다.
2. 덧셈
String [] sBits = s3.split("\\+");
int A = Integer.parseInt(sBits[0]);
int B = Integer.parseInt(sBits[1]);
String C = Integer.toString(A + B);
s1 = s1.replace(s2, C);
문자열을 쪼갠것을 A,B에 나누고 값을 C에 저장한다.
(10+5)를 결과값(C)으로 바꿔 준다. 그러면 (1+15*4)가 된다.
3. 곱셈 처리
if((s1.indexOf('*') != -1) || (s1.indexOf('/') != -1)) {
int indexFront = 0;
int indexLast = 0;
if(s1.indexOf('*') < s1.indexOf('/') || s1.indexOf('/')==-1) {
// 연산자 기준으로 왼쪽
for(int i = s1.indexOf('*')-1; i > -1; i--) {
if(s1.charAt(i) == '+' || s1.charAt(i) == '-' || s1.charAt(i) == '*' || s1.charAt(i) == '/') {
indexFront = i+1;
break;
}
else if(s1.charAt(i) >= '0' && s1.charAt(i) <= '9' ) {
indexFront = i;
}
}
// 연산자 기준으로 오른쪽
for(int j = s1.indexOf('*')+1; j < s1.length(); j++) {
if(s1.charAt(j) == '+' || s1.charAt(j) == '-' || s1.charAt(j) == '*' || s1.charAt(j) == '/') {
indexLast = j-1;
break;
}
else if(s1.charAt(j) >= '0' && s1.charAt(j) <= '9' ) {
indexLast = j;
}
}
String divied = s1.substring(indexFront,indexLast+1);
String [] diviedBits = divied.split("\\*");
int A_d = Integer.parseInt(diviedBits[0]);
int B_d = Integer.parseInt(diviedBits[1]);
String C_d = Integer.toString(A_d * B_d);
s1 = s1.replace(divied, C_d);
}
}
사칙 연산에는 곱셈, 나눗셈을 먼저하고 더하기, 빼기를 하는 연산 순서가 있다.
그러기에 위의 식은 만약 곱셈이나 나눗셈이 계산하고자 하는 곳에 포함되어 있다면 실행된다.
처음 if 문 아래는 곱셈이 나눗셈보다 앞에 있는 경우에 계산하는 것이다.
만약 나눗셈을 계산하고 싶다면 두번째 if 문이 아닐경우 (나눗셈이 먼저라는 뜻)else if를 해주면 된다.
구하고싶은 연산자를 기준으로 앞뒤를 탐색한다.
앞에 연산자가 있을 경우 원하는 연산자 부터 앞에 나온 연산자까지 숫자 하나이다. (뒤도 마찬가지다.)
원하는 연산자 앞뒤로 나오는 연산자가 없다면 숫자가 있는 부분까지를 잘라내면 된다.
또한 곱셈한 결과를 1번에서 replace 해준 것 처럼 (1+15*4) 를 (1+60)으로 만들어준다.
4. 덧셈 처리
if((s1.indexOf('+') != -1) || (s1.indexOf('-') != -1)) {
int indexFront = 0;
int indexLast = 0;
if(s1.indexOf('+') < s1.indexOf('-') || s1.indexOf('-')==-1) {
// 연산자 기준으로 왼쪽
for(int i = s1.indexOf('+')-1; i > -1; i--) {
if(s1.charAt(i) == '+' || s1.charAt(i) == '-' || s1.charAt(i) == '*' || s1.charAt(i) == '/') {
indexFront = i+1;
break;
}
else if(s1.charAt(i) >= '0' && s1.charAt(i) <= '9' ) {
indexFront = i;
}
}
// 연산자 기준으로 오른쪽
for(int j = s1.indexOf('+')+1; j < s1.length(); j++) {
if(s1.charAt(j) == '+' || s1.charAt(j) == '-' || s1.charAt(j) == '*' || s1.charAt(j) == '/') {
indexLast = j-1;
break;
}
else if(s1.charAt(j) >= '0' && s1.charAt(j) <= '9' ) {
indexLast = j;
}
}
String plus = s1.substring(indexFront,indexLast+1);
String [] plusBits = plus.split("\\+");
int A_p = Integer.parseInt(plusBits[0]);
int B_p = Integer.parseInt(plusBits[1]);
String C_p = Integer.toString(A_p + B_p);
s1 = s1.replace(plus, C_p);
}
}
3단계와 로직은 같다. +와 -를 *와 /대신에 넣어 준 것이고 마찬가지로 뺄셈은 나눗셈을 추가한것과 같이 추가해주면 된다.
5. 맨 마지막 괄호 제거
while과 indexOf, substring을 이용해 괄호가 없을 때 까지 괄호를 벗겨주면 되고, 구현은 쉽게 할 수 있을거라 생각하여 구현하지 않았다.
6. 전체
package noStack;
public class test {
public static void main(String[] args) {
String s1 = "(1+(10+5)* 4)";
s1 = s1.replace(" ", "");
String s2 = s1.substring(s1.lastIndexOf('('), s1.indexOf(')')+1);
String s3 = s1.substring(s1.lastIndexOf('(')+1, s1.indexOf(')'));
System.out.println(s2);
System.out.println(s3);
// 1단계 괄호가 있는 부분만 가져오기
String [] sBits = s3.split("\\+");
int A = Integer.parseInt(sBits[0]);
int B = Integer.parseInt(sBits[1]);
String C = Integer.toString(A + B);
s1 = s1.replace(s2, C);
System.out.println(s1);
// System.out.println(s1.indexOf('*'));
// System.out.println(s1.length());
// 2단계 괄호가 있는 부분 먼저 계산하고 결과를 원래 문자열에 변환해서 저장하기
if((s1.indexOf('*') != -1) || (s1.indexOf('/') != -1)) {
int indexFront = 0;
int indexLast = 0;
if(s1.indexOf('*') < s1.indexOf('/') || s1.indexOf('/')==-1) {
// 연산자 기준으로 왼쪽
for(int i = s1.indexOf('*')-1; i > -1; i--) {
if(s1.charAt(i) == '+' || s1.charAt(i) == '-' || s1.charAt(i) == '*' || s1.charAt(i) == '/') {
indexFront = i+1;
break;
}
else if(s1.charAt(i) >= '0' && s1.charAt(i) <= '9' ) {
indexFront = i;
}
}
// 연산자 기준으로 오른쪽
for(int j = s1.indexOf('*')+1; j < s1.length(); j++) {
if(s1.charAt(j) == '+' || s1.charAt(j) == '-' || s1.charAt(j) == '*' || s1.charAt(j) == '/') {
indexLast = j-1;
break;
}
else if(s1.charAt(j) >= '0' && s1.charAt(j) <= '9' ) {
indexLast = j;
}
}
String divied = s1.substring(indexFront,indexLast+1);
String [] diviedBits = divied.split("\\*");
int A_d = Integer.parseInt(diviedBits[0]);
int B_d = Integer.parseInt(diviedBits[1]);
String C_d = Integer.toString(A_d * B_d);
s1 = s1.replace(divied, C_d);
}
}
System.out.println(s1);
// 3단계 곱셈 일 경우 계산 처리 (나눗셈은 else를 통해 곱셈에서 한 부분을 복사해서 진행 하면된다.)
if((s1.indexOf('+') != -1) || (s1.indexOf('-') != -1)) {
int indexFront = 0;
int indexLast = 0;
if(s1.indexOf('+') < s1.indexOf('-') || s1.indexOf('-')==-1) {
// 연산자 기준으로 왼쪽
for(int i = s1.indexOf('+')-1; i > -1; i--) {
if(s1.charAt(i) == '+' || s1.charAt(i) == '-' || s1.charAt(i) == '*' || s1.charAt(i) == '/') {
indexFront = i+1;
break;
}
else if(s1.charAt(i) >= '0' && s1.charAt(i) <= '9' ) {
indexFront = i;
}
}
// 연산자 기준으로 오른쪽
for(int j = s1.indexOf('+')+1; j < s1.length(); j++) {
if(s1.charAt(j) == '+' || s1.charAt(j) == '-' || s1.charAt(j) == '*' || s1.charAt(j) == '/') {
indexLast = j-1;
break;
}
else if(s1.charAt(j) >= '0' && s1.charAt(j) <= '9' ) {
indexLast = j;
}
}
String plus = s1.substring(indexFront,indexLast+1);
String [] plusBits = plus.split("\\+");
int A_p = Integer.parseInt(plusBits[0]);
int B_p = Integer.parseInt(plusBits[1]);
String C_p = Integer.toString(A_p + B_p);
s1 = s1.replace(plus, C_p);
}
}
System.out.println(s1);
// 4단계 덧셈 완료 만약 마이너스를 넣고자 한다면 else를 통해 뺄셈을 넣으면 된다.
}
}
//출력 결과
(10+5)
10+5
(1+15*4)
(1+60)
(61)
(61)이 나온다.
스택 없이도 구현은 가능하다.
단, 반쪽짜리 임에도 불구하고 벌써 100줄이 넘는다.
그 만큼 로직이 복잡하다는 것이다.
때문에 스택 방법을 이용하는 것을 추천한다.
'자료구조 || 알고리즘' 카테고리의 다른 글
| 유클리드 호제법(최대공약수 구하기) (0) | 2022.06.25 |
|---|---|
| 좌표압축 (0) | 2022.06.18 |
| 트리와 전위,중위,후위 순회 (0) | 2022.06.11 |
| 스택(Stack)과 큐(Queue) (0) | 2022.06.11 |
| [자바] 문자열에서 사칙연산과 숫자 분리 (0) | 2022.06.09 |
'자료구조 || 알고리즘' Related Articles
more
Comments