표현 평가 문제에서 우리는 현 정수, 균형 괄호 및 이진 연산 (+,-, *, /)으로 구성 될 수있는 표현식을 나타내는 길이 n의 s. 식을 평가하십시오. 표현식은 접두사, 중위 또는 접미사 중 하나 일 수 있습니다. 표기법.
차례
예
표현식 평가에 대한 몇 가지 예를 참조하십시오.
입력 : s = "100 * (2 + 12)"
출력 : 1400
입력 : s = "10 + 2 * 6"
출력 : 22
식 평가를위한 알고리즘
이제 식 평가에 대한 문제 설명을 알았습니다. 그래서 우리는 시간을 낭비하지 않고 연산 식 평가 솔루션에 사용합니다.
- expression으로 구성된 길이 n의 문자열 s를 초기화합니다.
- 하나 생성 스택 값을 저장하고 다른 연산자를 저장합니다.
- 문자열을 가로 질러 현재 문자가 공백인지 확인하고 루프를 계속합니다. 그렇지 않으면 여는 괄호 인 경우 연산자 스택에 밀어 넣습니다.
- 그렇지 않으면 현재 문자가 숫자 인 경우. 정수 val을 0으로 초기화합니다. 현재 문자가 숫자 인 동안 현재 위치 + 1에서 문자열 끝까지 순회하고 val * 10 + 현재 숫자로 업데이트합니다. 가치 더미에 밀어 넣으십시오.
- 그렇지 않으면 닫는 괄호이면 연산자 스택이 비어 있지 않고 현재 문자가 여는 괄호가 아닌 동안 트래버스합니다.
- 값 스택에서 상위 2 개 숫자와 연산자 스택에서 연산자를 팝합니다. 산술 연산을 수행하고 결과를 값 스택으로 푸시합니다.
- 연산자 스택이 비어 있지 않은 동안 값 스택에서 상위 2 자리 숫자와 연산자 스택에서 연산자를 팝합니다. 산술 연산을 수행하고 결과를 값 스택으로 푸시합니다.
- 값 스택의 맨 위를 반환합니다.
식 평가를위한 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int precedence(char op){
if(op == '+'||op == '-')
return 1;
if(op == '*'||op == '/')
return 2;
return 0;
}
int applyOp(int a, int b, char op){
switch(op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
}
int evaluate(string tokens){
int i;
stack <int> values;
stack <char> ops;
for(i = 0; i < tokens.length(); i++){
if(tokens[i] == ' ')
continue;
else if(tokens[i] == '('){
ops.push(tokens[i]);
}
else if(isdigit(tokens[i])){
int val = 0;
while(i < tokens.length() && isdigit(tokens[i])){
val = (val*10) + (tokens[i]-'0');
i++;
}
values.push(val);
}
else if(tokens[i] == ')'){
while(!ops.empty() && ops.top() != '('){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
if(!ops.empty())
ops.pop();
}
else{
while(!ops.empty() && precedence(ops.top()) >= precedence(tokens[i])){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
return values.top();
}
int main(){
cout << evaluate("100 * ( 2 + 12 )") << endl;
return 0;
}
1400
표현식 평가를위한 Java 프로그램
import java.util.Stack;
class EvaluateString{
public static int evaluate(String expression){
char[] tokens = expression.toCharArray();
Stack<Integer> values = new Stack<Integer>();
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++){
if(tokens[i] == ' ')
continue;
if(tokens[i] >= '0' && tokens[i] <= '9'){
StringBuffer sbuf = new StringBuffer();
while(i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
sbuf.append(tokens[i++]);
}
values.push(Integer.parseInt(sbuf.toString()));
}
else if(tokens[i] == '(')
ops.push(tokens[i]);
else if(tokens[i] == ')'){
while (ops.peek() != '('){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.pop();
}
else if(tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/'){
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek())){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
}
return values.pop();
}
public static boolean hasPrecedence(char op1, char op2){
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
public static int applyOp(char op, int b, int a){
switch (op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
public static void main(String[] args){
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
}
}
1400
복잡성 분석
시간 복잡성 : O (n) 여기서 n은 평가할 표현식의 길이입니다.
공간 복잡성 : n 문자를 저장하는 데 필요한 공간이므로 O (n).
