Problem F - Calculator

Time Limit: 1 second

You are an employee of a company which produces calculators. Your company is developing an outstanding new calculator, and you are developing the software of that new calculator. This calculator is intended for people that would like to save intermediate values in the memory for future use. For this reason, this new calculator has space for 26 values in its memory, named a to z. Those values are stored with double precision.

For simplicity, here we will consider only the four basic operations, sum, minus, multiply and divide (+ - * /). Also, expressions can be grouped with parenthesis. You should consider the precedence of operations, with multiplication and division first, then addition and subtraction. Also, only integer numbers and the letters a to z will appear on the expression, along with the symbols of the operations, the parenthesis and the equal sign for attribution.

Input

The input consists of an undetermined number of lines, with one expression per line. One expression can be an attribution or a question. If the expression is an attribution it will begin with X=, where X is the letter representing the memory space and a ≤ X ≤ z. If the expression is not an attribution expression, then it is a question. There will be no blank spaces in the expression. You will only produce output for the questions.

The input will end with the end of file (EOF).

Output

For each question, print it's evaluated value on a line by itself. Print the result rounded to two decimal places. See sample input/output for the exact format.

Sample Input

x=10
x
x+10
x/5
x/2
x/3
y=5/3
y
x*y
x-y

Sample Output

10.00
20.00
2.00
5.00
3.33
1.67
16.67
8.33

---

Problem setter: Jo�o Paulo Fernandes Farias


模板拿出，處理一下流程就可以了。

#include <iostream>
#include <sstream> // stringstream
#include <ctype.h> // isdigit()
#include <stdio.h>
#include <algorithm>
using namespace std;
//<stack template>
template <typename T>
struct Node {
    T d;
    Node *prev;
};
template <class T>
class STACK { // linked list implements stack
    public:
        STACK() {
            idx = NULL;
            SIZE = 0;
        }
        T top() {
            T cpy = idx->d;
            return cpy;
        }
        void pop() {
            Node<T> *tmp;
            tmp = idx;
            idx = idx->prev;
            delete tmp;
            SIZE--;
        }
        void push(T item) {
            Node<T> *nd = new Node<T>;
            nd->d = item;
            nd->prev = idx;
            idx = nd;
            SIZE++;
        }
        bool empty() {
            return idx == NULL;
        }
        int size() {
            return SIZE;
        }
    private:
        Node<T> *idx;
        int SIZE;
};
//</stack template>
//<parse infix>
int priority(char c) {
    switch(c) {
        case '(':return 1;
        case '+':return 2;
        case '-':return 2;
        case '*':return 3;
        case '/':return 3;
    }
    return -1; // error state
}
string infix2postfix(string infix) {
    string postfix = "";
    int i, j, len = infix.length();
    STACK<char> opStk; // save operator, not number
    for(i = 0; i < len; i++) {
        if(infix[i] == ' ')
            continue;
        if(isdigit(infix[i]) || isalpha(infix[i])) { // cut number
            while(i < len && (isdigit(infix[i]) || isalpha(infix[i]))) {
                postfix += infix[i];
                i++;
            }
            i--; // because for loop i++
            postfix += ' ';
        } else { // operator or '(' or ')'
            if(infix[i] == ')') {
                while(opStk.top() != '(') {
                    postfix += opStk.top();
                    postfix += ' ';
                    opStk.pop();
                }
                opStk.pop(); // pop '('
            } else {
                while(!opStk.empty() && infix[i] != '(') {
                    if(opStk.top() != '(') {
                        if(priority(opStk.top()) >= priority(infix[i])) {
                            postfix += opStk.top();
                            postfix += ' ';
                            opStk.pop();
                        } else
                            break;
                    } else
                        break;
                }
                opStk.push(infix[i]);
            }
        }
    }
    while(!opStk.empty()) {
        postfix += opStk.top();
        postfix += ' ';
        opStk.pop();
    }
    return postfix;
}
//</parse infix>
//<calc postfix>
double assign_val[26];
double calcPostfix(string postfix) {
    STACK<double> stk;
    stringstream sin(postfix);
    string token;
    double a, b;
    while(sin >> token) {
        switch(token[0]) {
            case '+': case '-': case '*': case '/':
                b = stk.top(), stk.pop();
                a = stk.top(), stk.pop();
                if(token == "+")
                    stk.push(a+b);
                if(token == "-")
                    stk.push(a-b);
                if(token == "*")
                    stk.push(a*b);
                if(token == "/")
                    stk.push(a/b);
                break;
            default:
                if(token[0] >= 'a' && token[0] <= 'z')
                    a = assign_val[token[0]-'a'];
                else {
                    stringstream sin(token);
                    sin >> a;
                }
                stk.push(a);
        }
    }
    return stk.top();
}
//</calc postfix>
int main() {
    string line;
    while(getline(cin, line)) {
        if(line[1] == '=') {
            string postfix = infix2postfix(line.substr(2));
            int val = line[0]-'a';
            assign_val[val] = calcPostfix(postfix);
        } else {
            string postfix = infix2postfix(line);
            printf("%.2lf\n", calcPostfix(postfix));
        }
    }
    return 0;
}