题目描述

表达式求值，只不过在加减乘除的基础上加了普通函数调用f(a,b)和成员函数调用a.f(a,b)两种形式。需要输出计算过程

样例

(a+f((b-c+e)*d/c.h(d,d)).g(e)).g(d).h(f(a,c),f(b)/f(c),f(d))

- b c
+ 1 e
* 2 d
h c d d
/ 3 4
f 5
g 6 e
+ a 7
g 8 d
f a c
f b
f c
/ 11 12
f d
h 9 10 13 14

思路

我只拿到了4/10的分数，所以也不算真正意义的题解，这是因为因为我目前只考虑了加减乘除和括号的情况，没有考虑函数调用。
如果只考虑加减乘除和括号的情况会简单很多，我先把表达式转为后缀表达式，然后用后缀表达式求值的思路（栈）输出了计算过程。
如果想拿满分的话确实要用到编译原理中递归下降语法分析的知识构建语法分析树，在进行递归分析的时候关键是要确定按照哪种形式分解（是按照成员函数调用还是普通函数调用？），我目前觉得可以用正则匹配来确定。

4/10代码

#include <iostream>
#include <stack>
#include<vector>
#include<string.h>
using namespace std;
// 判断是否是操作符
bool isOperator(char ch) {
    if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
        return true;
    return false; // 否则返回false
}

// 获取优先级
int getPriority(char ch) {
    int level = 0; // 优先级

    switch(ch) {
        case '(':
            level = 1;
            break;
        case '+':
        case '-':
            level = 2;
            break;
        case '*':
        case '/':
            level = 3;
            break;
        default:
            break;
    }
    return level;
}
//输出后缀表达式计算过程
void evalRPN(vector<string>& tokens) {
    int order=1;//表明标识这是第几个计算结果（和题目相关）
    stack<string>numst;
    for(int i = 0;i<tokens.size();++i)
    {
        string c = tokens[i] ;
        if(c == "+"||c == "-"||c == "*"||c == "/" ) //如果是运算符，那么运算
        {
            string temp1 = numst.top(); numst.pop();
            string temp2 = numst.top(); numst.pop();
            string temp3 = to_string(order);
            order++;
            cout<<c<<" "<<temp2<<" "<<temp1<<endl;
            numst.push(temp3);
        }
        else
        {//如果是运算数，直接push
        numst.push(c);
        }
    }
};

int main(int argc, const char * argv[]) {
    // insert code here...
    int num;
    char arr[250]; // 一个一个的读取表达式，直到遇到'\0'
    std::stack<char> op; // 栈op:存储操作符
    vector<string>hou_zhui;//存储后缀表达式
    std::cin.getline(arr,250);
    int len, i;
    char c; // c存储从栈中取出的操作符

    len = (int)strlen(arr); // strlen()输出的是：unsigned long类型，所以要强制转换为int类型
    i = 0;
    while(i < len) {
        if((arr[i]>=97)&&(arr[i]<=122)) { // 如果是小写字母
            hou_zhui.push_back(string(1,arr[i]));
            i++;
        }

        else if(arr[i] == '(') { // (:左括号
            op.push(arr[i]);
            i++;
        } else if(isOperator(arr[i])) { // 操作符
            if(op.empty()) {// 如果栈空，直接压入栈
                op.push(arr[i]);
                i++;
            }
            else {
                // 比较栈op顶的操作符与ch的优先级
                // 如果ch的优先级高，则直接压入栈
                // 否则，推出栈中的操作符，直到操作符小于ch的优先级，或者遇到（，或者栈已空
                while(!op.empty()) {
                    c = op.top();
                    if(getPriority(arr[i]) <= getPriority(c)) {
                        hou_zhui.push_back(string(1,c));
                        op.pop();
                    } else // ch优先级高于栈中操作符
                        break;
                } // while结束
                op.push(arr[i]); // 防止不断的推出操作符，最后空栈了;或者ch优先级高了
                i++;
            } // else
        } else if(arr[i] == ')') { // 如果是右括号，一直推出栈中操作符，直到遇到左括号(
            while(op.top() != '(') {
                hou_zhui.push_back(string(1,op.top()));
                op.pop();
            }
            op.pop(); // 把左括号(推出栈
            i++;
        } else // 如果是空白符，就进行下一个字符的处理
            i++;
    } // 第二个while结束
    while(!op.empty()) { // 当栈不空，继续输出操作符
        hou_zhui.push_back(string(1,op.top()));
        op.pop();
    }

    evalRPN(hou_zhui);

    return 0;
}