【题目链接】

ybt 1356：计算(calc)

【题目考点】

1. 表达式求值

中缀表达式求值

讯享网

2. 表达式树

struct Node { 
    char c;//运算符 int n;//数值 } 

• 分支结点：c:运算符，n:该子树对应的表达式的值
• 叶子结点：c:'\0'，n:数值
  表达式树的值，是左子树的值和右子树的值，经过根结点运算符运算后得到的结果。

【解题思路】

解法1：中缀表达式直接求值

1. 设数字栈、运算符栈。设数组表示运算符优先级，其中'('优先级最高，')'优先级最低。
   从左向右扫描表达式字符串：
2. 遇到数字时，入数字栈。
3. 遇到运算符时，入栈条件为：栈空，或该运算符优先级比栈顶运算符优先级高，或者栈顶是'('。只有不满足该条件，则一直出栈。
   运算符出栈后，数字栈出栈两个数字，加上刚刚出栈的运算符进行一次运算，将运算结果加入数字栈。
   如果要入栈的是')'且栈顶是'('，那么二者配对，出栈运算符。否则运算符入栈。
4. 扫描结束后若栈中有运算符，都出栈。
5. 最后数字栈中的数字即为整个中缀表达式的运算结果
   可以预先在字符串末尾加上一个优先级最低的')'，以促使运算符栈中的运算符都出栈。

解法2：中缀表达式转为后缀表达式，而后求值。

中缀表达式转后缀表达式：

1. 设数组保存后缀表达式，设运算符栈。
   从左向右扫描表达式字符串：
2. 遇到数字时，将数字添加到后缀表达式
3. 遇到运算符时，入栈条件为：栈空，或该运算符优先级比栈顶运算符优先级高，或者栈顶是'('。只有不满足该条件，则一直出栈。出栈的运算符添加到后缀表达式。
4. 扫描结束后若栈中有运算符，都出栈，加入后缀表达式。
   可以预先在字符串末尾加上一个优先级最低的')'，以促使运算符栈中的运算符都出栈。
   而后求解后缀表达式，后缀表达式的求解方法见：信息学奥赛一本通 1331：【例1-2】后缀表达式的值

解法3：建立表达式树

1. 设结点栈、运算符栈。设数组表示运算符优先级，其中'('优先级最高，')'优先级最低。
   从左向右扫描表达式字符串：
2. 遇到数字时，构建数字结点，将结点地址加入结点栈。
3. 遇到运算符时，入栈条件为：栈空，或该运算符优先级比栈顶运算符优先级高，或者栈顶是'('。只有不满足该条件，则一直出栈。
   运算符出栈后，从结点池申请新结点作为这棵子树的根结点，该结点的运算符属性为出栈的运算符，结点栈出栈两个结点a, b作为该结点的左右孩子，使用左右孩子的值结合该结点的运算符进行运算，结果设为该结点的值，将该结点的地址入栈结点栈。
   如果要入栈的是')'且栈顶是'('，那么二者配对，出栈运算符。否则运算符入栈。
4. 扫描结束后若栈中有运算符，都出栈。
5. 最后结点栈的栈顶即为整个中缀表达式建树得到的树的根结点，该结点的值即为整个表达式的值。
   可以预先在字符串末尾加上一个优先级最低的')'，以促使运算符栈中的运算符都出栈。

【题解代码】

解法1：中缀表达式直接求值

讯享网#include <bits/stdc++.h> using namespace std; int pri(char c)//返回c的优先级  { 
    switch(c) { 
    case '(': return 5; case '^': return 4; case '*': case '/': return 3; case '+': case '-': return 2; case ')': return 1; } } int calc(int a, int b, char c) { 
    switch(c) { 
    case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; case '^': return pow(a, b); } } int main() { 
    stack<int> nStk; stack<char> cStk; int num = 0; bool isNum; string s; cin >> s; s.push_back(')'); for(int i = 0; i < s.length(); ++i) { 
    if(s[i] >= '0' && s[i] <= '9') { 
    num = num*10+s[i]-'0'; isNum = true; } else//s[i]是运算符  { 
    if(isNum) { 
    nStk.push(num); num = 0; isNum = false; } while(!(cStk.empty() || pri(s[i]) > pri(cStk.top()) || cStk.top() == '(')) { 
   //运算符栈出栈  int b = nStk.top(); nStk.pop(); int a = nStk.top(); nStk.pop(); nStk.push(calc(a, b, cStk.top())); cStk.pop(); } if(!cStk.empty() && cStk.top() == '(' && s[i] == ')') cStk.pop(); else cStk.push(s[i]); } } cout << nStk.top(); return 0; } 

解法2：中缀表达式转为后缀表达式，而后求值。

#include <bits/stdc++.h> using namespace std; #define N 1005 struct Node { 
    int n; char c; } eq[N]; int p, ei; int pri(char c) { 
    switch(c) { 
    case '(' : return 5; case '^' : return 4;//2^3 case '*': case '/': return 3; case '+': case '-': return 2; case ')': return 1; } } int calc(int a, int b, char c) { 
    switch(c) { 
    case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; case '^': return pow(a, b); } } int solve() { 
    int i = ei--; if(eq[i].c) { 
    int b = solve(); int a = solve(); return calc(a, b, eq[i].c); } else return eq[i].n; } int main() { 
    stack<char> cStk; bool isNum = false;//当前是否在构建数字  int num = 0; string s; cin >> s; s += ')';//s.push_back(')'); for(int i = 0; i < s.length(); ++i) { 
    if(s[i] >= '0' && s[i] <= '9') { 
    num = num*10+s[i]-'0'; isNum = true; } else { 
    if(isNum) { 
    eq[++p].n = num; num = 0; isNum = false; } while(!(cStk.empty() || pri(s[i]) > pri(cStk.top()) || cStk.top() == '('))//!(入栈条件) { 
   //出栈运算符  eq[++p].c = cStk.top(); cStk.pop(); } if(cStk.empty() == false && cStk.top() == '(' && s[i] == ')') cStk.pop(); else cStk.push(s[i]); } } ei = p; cout << solve(); return 0; } 

解法3：建立表达式树

讯享网#include <bits/stdc++.h> using namespace std; struct Node { 
    int n; char c; int left, right; } node[1005]; int p; int pri(char c)//返回运算符c的优先级  { 
    switch(c) { 
    case '(': return 5; case '^': return 4; case '*': case '/': return 3; case '+': case '-': return 2; case ')': return 1; } } int calc(int a, int b, char c) { 
    switch(c) { 
    case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; case '^': return pow(a, b); } } int main() { 
    stack<int> nStk;//结点地址栈  stack<char> cStk;//运算符栈  bool isNum = false; int num = 0; string s; cin >> s; s += ')'; for(int i = 0; i < s.length(); ++i) { 
    if(s[i] >= '0' && s[i] <= '9') { 
    num = num*10+s[i]-'0'; isNum = true; } else { 
    if(isNum) { 
    int np = ++p; node[np].n = num; nStk.push(np); num = 0; isNum = false; } while(!(cStk.empty() || pri(s[i]) > pri(cStk.top()) || cStk.top() == '(')) { 
    int np = ++p; node[np].c = cStk.top(); int b = nStk.top(); nStk.pop(); int a = nStk.top(); nStk.pop(); node[np].left = a, node[np].right = b; node[np].n = calc(node[a].n, node[b].n, node[np].c); nStk.push(np); cStk.pop(); } if(s[i] == ')') cStk.pop(); else cStk.push(s[i]); } } int root = nStk.top(); cout << node[root].n; return 0; }