후위 표기법

후위표기법 

검색해보니 이상하고 난잡한 소스들이 많은 것 같다. 우선순위를 구하는 함수를 따로 두질 않나..

그나마 이게 제일 깔끔해보임.

3+4+5*6+7

34+56*+7+

#include<stdio.h>

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int main()

{

string dump;

int t = 0, size;

std::vector<char> v;

vector<int> result;

std::string post = "";

while (t++ < 10)

{

scanf("%d", &size);

cin >> dump;

for (int i = 0; i < size; i++) {

switch (dump[i])

{

case '(':

v.push_back(dump[i]);

break;

case ')':

while (v.back() != '(')

{

post += v.back();

v.pop_back();

}

v.pop_back();

break;

case '+':

case '-':

while (!v.empty() && v.back() != '(')

{

post += v.back();

v.pop_back();

}

v.push_back(dump[i]);

break;

case '*':

case '/':

while (!v.empty() && (v.back() == '*' || v.back() == '/'))

{

post += v.back();

v.pop_back();

}

v.push_back(dump[i]);

break;

default:

post += dump[i];

break;

}

}

while (!v.empty())

{

post += v.back();

v.pop_back();

}

for (int i = 0; i < post.size(); i++)

{

switch (post[i])

{

case '+': 

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 + op2);

break;

}

case '*':

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 * op2);

break;

}

case '/':

{

int op1 = result.back();

result.pop_back();

int  op2 = result.back();

result.pop_back();

result.push_back(op1 / op2);

break;

}

default:

result.push_back(post[i] - '0');

break;

}

}

printf("#%d %d\n", t, result.back());

result.pop_back();

}

return 0;

}