输入一个中缀表达式(由 0 ∼ 9 0∼9 组成的运算数、加 + 减 - 乘 * 除 / 四种运算符、左右小括号组成。注意 - 也可作为负数的标志,表达式以 @ 作为结束符),判断表达式是否合法,如果不合法,请输出 NO;否则请把表达式转换成后缀形式,再求出后缀表达式的值并输出。
时间: 2024-04-17 22:26:15 浏览: 224
中缀表达式的计算(判断表达式是否合法)
好的,我会帮你实现这个功能。以下是代码实现:
```cpp
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cmath>
using namespace std;
int priority(char op) {
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else if (op == '^')
return 3;
else
return 0;
}
bool isValidExpression(const string& expression) {
stack<char> brackets;
for (char c : expression) {
if (c == '(')
brackets.push(c);
else if (c == ')') {
if (brackets.empty() || brackets.top() != '(')
return false;
brackets.pop();
}
}
return brackets.empty();
}
double evaluatePostfix(const string& postfix) {
stack<double> operands;
for (char c : postfix) {
if (isdigit(c)) {
operands.push(c - '0');
} else {
double operand2 = operands.top();
operands.pop();
double operand1 = operands.top();
operands.pop();
double result;
switch(c) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
case '^':
result = pow(operand1, operand2);
break;
default:
return 0; // should never reach here
}
operands.push(result);
}
}
return operands.top();
}
string infixToPostfix(const string& infix) {
string postfix;
stack<char> operators;
for (char c : infix) {
if (isdigit(c)) {
postfix += c;
} else if (c == '(') {
operators.push(c);
} else if (c == ')') {
while (!operators.empty() && operators.top() != '(') {
postfix += operators.top();
operators.pop();
}
if (!operators.empty() && operators.top() == '(')
operators.pop(); // pop '('
else
return ""; // mismatched parentheses
} else {
while (!operators.empty() && priority(operators.top()) >= priority(c)) {
postfix += operators.top();
operators.pop();
}
operators.push(c);
}
}
while (!operators.empty()) {
postfix += operators.top();
operators.pop();
}
return postfix;
}
int main() {
string expression;
cin >> expression;
if (!isValidExpression(expression)) {
cout << "NO" << endl;
return 0;
}
string postfix = infixToPostfix(expression);
if (postfix == "") {
cout << "NO" << endl;
return 0;
}
double result = evaluatePostfix(postfix);
cout << result << endl;
return 0;
}
```
这段代码首先定义了几个辅助函数:`priority()`用于返回运算符的优先级,`isValidExpression()`用于判断表达式中的括号是否匹配,`evaluatePostfix()`用于计算后缀表达式的值,`infixToPostfix()`用于将中缀表达式转换为后缀表达式。
在`main()`函数中,首先读取输入的中缀表达式。然后使用`isValidExpression()`函数判断表达式是否合法,如果不合法则输出"NO"。接着使用`infixToPostfix()`函数将中缀表达式转换为后缀表达式,如果转换失败(例如括号不匹配),则也输出"NO"。最后使用`evaluatePostfix()`函数计算后缀表达式的值,并输出结果。
请注意,在输入中缀表达式时,需要在表达式末尾添加一个结束符"@ ",以便程序正确处理输入。例如,输入"1+2*3@"表示1+2*3这个表达式。
希望这个代码能够满足你的需求!如果有任何问题,请随时提问。
阅读全文