从标准输入中读入一个整数算术运算表达式,如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ,计算表达式结果,并输出。 要求: 1、表达式运算符只有+、-、*、/,表达式末尾的=字符表示表达式输入结束,表达式中可能会出现空格; 2、表达式中会出现圆括号,括号可能嵌套,不会出现错误的表达式; 3、出现除号/时,以整数相除进行运算,结果仍为整数,例如:5/3结果应为1。 4、要求采用表达式树来实现表达式计算。
时间: 2023-07-14 19:11:55 浏览: 316
字符串中加减法main.c
这道题目可以通过表达式树来实现,具体思路如下:
1. 定义一个节点结构体,包含一个值和左右子节点指针。
2. 读入表达式并去除空格,将其转换为后缀表达式,同时构建表达式树。具体方法可以使用栈来实现。
3. 对表达式树进行遍历计算,将结果返回。
下面是一份参考代码,仅供参考。
```c++
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
// 节点结构体
struct Node {
char val;
Node* left;
Node* right;
Node(char v): val(v), left(nullptr), right(nullptr) {}
};
// 判断是否为操作符
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 获取操作符优先级
int getPriority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}
// 将中缀表达式转换为后缀表达式
string infix2postfix(string s) {
stack<char> st;
string res = "";
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (isdigit(c)) {
res += c;
} else if (c == '(') {
st.push(c);
} else if (c == ')') {
while (!st.empty() && st.top() != '(') {
res += st.top();
st.pop();
}
st.pop();
} else if (isOperator(c)) {
while (!st.empty() && getPriority(c) <= getPriority(st.top())) {
res += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty()) {
res += st.top();
st.pop();
}
return res;
}
// 构建表达式树
Node* buildExpressionTree(string postfix) {
stack<Node*> st;
for (int i = 0; i < postfix.length(); i++) {
char c = postfix[i];
if (isdigit(c)) {
st.push(new Node(c));
} else if (isOperator(c)) {
Node* node = new Node(c);
node->right = st.top();
st.pop();
node->left = st.top();
st.pop();
st.push(node);
}
}
return st.top();
}
// 计算表达式树的值
int calculateExpressionTree(Node* root) {
if (!root) {
return 0;
}
if (isdigit(root->val)) {
return root->val - '0';
}
int left = calculateExpressionTree(root->left);
int right = calculateExpressionTree(root->right);
switch (root->val) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
}
return 0;
}
int main() {
string s;
getline(cin, s);
s.erase(remove_if(s.begin(), s.end(), ::isspace), s.end()); // 去除空格
s = infix2postfix(s.substr(0, s.length() - 1)); // 转换为后缀表达式
Node* root = buildExpressionTree(s); // 构建表达式树
int res = calculateExpressionTree(root); // 计算表达式树的值
cout << res << endl;
return 0;
}
```
阅读全文