#include <iostream>
#include <stack>
#include <cstdlib>
#include <cctype>
#include <queue>
#include <cassert>
#include <fstream>
#define MAXN 1000000
#define PARENTHESIS 2
#define UNARY_PLUS_AND_MINUS 3
#define LOGICAL_NOT 3
#define BIT_NOT 3
#define MULT_DIV_MOD 5
#define ADD_AND_SUB 6
#define BIT_LEFT_AND_RIGHT 7
#define BIT_AND 10
#define BIT_EXCLUSIVE 11
#define BIT_OR 12
#define LOGICAL_AND 13
#define LOGICAL_OR 14
using namespace std;
typedef struct component
{
string symbol;
int priority;
}Component;
using namespace std;
string removeSpace(string line)
{
for(int i = 0; i < line.length(); i++)
if(line.at(i) == ' ')
{
line.erase(i, 1);
i--;
}
return line;
}
bool isNumber(string line)
{
if(line.length() == 1 && (line[0] == '+' || line[0] == '-'))
return false;
for(int i = 0; i < line.length(); i++)
{
if(!(isdigit(line[i]) || line[i] == '+' || line[i] == '-'))
return false;
}
return true;
}
int toNumber(string line)
{
int number = 0;
for(int i = line.length() - 1, j = 1; i >= 0; i--, j *= 10)
{
if(line[i] == '+');
else if(line[i] == '-')
number *= -1;
else
number += j * (line[i] - '0');
}
return number;
}
string readNumber(string operation, int& index)
{
string buffer;
while(index < operation.length() && isdigit(operation.at(index)) )
{
buffer += operation.at(index);
index++;
}
return buffer;
}
void check_and_push(stack<Component>& bufferStack, queue<string>& postfix, Component component)
{
while((!bufferStack.empty()) && bufferStack.top().priority <= component.priority && bufferStack.top().symbol != "(")
{
if(component.priority == 3 && bufferStack.top().priority == 3)
break;
postfix.push(bufferStack.top().symbol);
bufferStack.pop();
}
bufferStack.push(component);
}
void pop_all(stack<Component>& bufferStack, queue<string>& postfix)
{
while(bufferStack.top().symbol != "(")
{
postfix.push(bufferStack.top().symbol);
bufferStack.pop();
}
bufferStack.pop();
}
void traverseLine(string operation, stack<Component>& bufferStack, queue<string>& postfix, int& index)
{
Component component;
string buffer;
if(operation.at(index) == ')')
{
index++;
pop_all(bufferStack, postfix);
return;
}
// read number
if(isdigit(operation.at(index)))
{
buffer = readNumber(operation, index);
postfix.push(buffer);
}
else if(operation.at(index) == '+' || operation.at(index) == '-')
{
// unary plus and minus
if(index == 0 || (!isdigit(operation.at(index - 1)) && operation.at(index - 1) != ')'))
{
component.symbol += operation.at(index);
component.symbol += "PM";
index++;
component.priority = UNARY_PLUS_AND_MINUS;
}
// addtion and substraction
else
{
component.symbol = operation.at(index);
index++;
component.priority = ADD_AND_SUB;
}
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '*' || operation.at(index) == '/' || operation.at(index) == '%')
{
component.symbol = operation.at(index);
index++;
component.priority = MULT_DIV_MOD;
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '!')
{
component.symbol = "!";
index++;
component.priority = LOGICAL_NOT;
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '~')
{
component.symbol = "~";
index++;
component.priority = BIT_NOT;
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '&')
{
if(operation.at(index + 1) == '&')
{
component.symbol = "&&";
index += 2;
component.priority = LOGICAL_AND;
}
else
{
component.symbol = "&";
index++;
component.priority = BIT_AND;
}
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '|')
{
if(operation.at(index + 1) == '|')
{
component.symbol = "||";
index += 2;
component.priority = LOGICAL_OR;
}
else
{
component.symbol = "|";
index++;
component.priority = BIT_OR;
}
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '<' || operation.at(index) == '>')
{
component.symbol += operation.at(index); component.symbol += operation.at(index);
index += 2;
component.priority = BIT_LEFT_AND_RIGHT;
check_and_push(bufferStack, postfix, component);
}
else if(operation.at(index) == '^')
{
component.symbol = "^";
index++;
component.priority = BIT_EXCLUSIVE;
check_and_push(bufferStack, postfix, component);
}
else
{
if(operation.at(index) != '(')
{
cout << operation.at(index);
exit(-1);
}
else
{
component.symbol = "(";
index++;
component.priority = PARENTHESIS;
check_and_push(bufferStack, postfix, component);
traverseLine(operation, bufferStack, postfix, index);
}
}
}
void printPostfix(queue<string>& postfix, deque<string>& calculator)
{
cout << "Postfix Exp: ";
while(!postfix.empty())
{
if(postfix.front().length() >= 3)
cout << postfix.front().at(0) << " ";
else
cout << postfix.front() << " ";
calculator.push_front(postfix.front());
postfix.pop();
}
cout << endl;
}
int calculate(deque<string>& calculator)
{
stack<int> buffer;
while(!calculator.empty())
{
if(isNumber(calculator.back()))
{
buffer.push(toNumber(calculator.back()));
calculator.pop_back();
}
else if(calculator.back() == "*")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b * a);
}
else if(calculator.back() == "/")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b / a);
}
else if(calculator.back().at(0) == '%')
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b % a);
}
else if(calculator.back() == "+PM")
{
calculator.pop_back();
}
else if(calculator.back() == "-PM")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
buffer.push(-a);
}
else if(calculator.back() == "+")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b + a);
}
else if(calculator.back() == "-")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b - a);
}
else if(calculator.back() == "&")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b & a);
}
else if(calculator.back() == "^")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b ^ a);
}
else if(calculator.back() == "|")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b | a);
}
else if(calculator.back() == ">>")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b >> a);
}
else if(calculator.back() == "<<")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b << a);
}
else if(calculator.back() == "~")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
buffer.push(~a);
}
else if(calculator.back() == "&&")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b && a);
}
else if(calculator.back() == "||")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
int b = buffer.top(); buffer.pop();
buffer.push(b || a);
}
else if(calculator.back() == "!")
{
calculator.pop_back();
int a = buffer.top(); buffer.pop();
buffer.push(!a);
}
}
return buffer.top();
}
int main(void)
{
string operation; stack<Component> bufferStack; queue<string> postfix; deque<string> calculator;
while(getline(cin, operation))
{
operation = removeSpace(operation);
int index = 0;
while(index < operation.length())
traverseLine(operation, bufferStack, postfix, index);
while(!bufferStack.empty())
{
postfix.push(bufferStack.top().symbol);
bufferStack.pop();
}
printPostfix(postfix, calculator);
cout << "RESULT: " << calculate(calculator) << endl;
assert(bufferStack.empty() && postfix.empty() && calculator.empty());
}
}