(5) 【编程题】算术表达式求值。演示程序和源程序已给出。用户从键盘输入一个算术表达式,数字都是十进制整型(必须支持负数),运算符支持+-*/()。 编写源程序中的 double deal_exp (char *exp) 函数,对这个算术表达式求值,返回结果。不限制方法,你可以用“原始”的多遍扫描字符串,也可以用先进一点的栈(本课程前面接触的栈都是操作系统提供给程序以实现局部变量定义和函数调用的,现在你需要自己创建并使用栈了)。为便于集中精力在功能方面,可以不用检查用户输入的合法性。
时间: 2024-02-01 21:14:01 浏览: 42
以下是一个使用栈的算术表达式求值的示例代码:
```c++
#include <iostream>
#include <stack>
#include <cstring>
#include <cmath>
using namespace std;
double deal_op(double a, double b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return pow(a, b);
default:
return 0;
}
}
int get_priority(char op) {
switch (op) {
case '(':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}
double deal_exp(char *exp) {
stack<double> num_stack;
stack<char> op_stack;
int len = strlen(exp);
char *p = exp;
while (p < exp + len) {
if (*p == ' ') {
p++;
continue;
}
if (isdigit(*p) || *p == '.') {
char *q = p;
while (isdigit(*q) || *q == '.') {
q++;
}
double num = stod(string(p, q));
num_stack.push(num);
p = q;
continue;
}
if (*p == '(') {
op_stack.push(*p);
p++;
continue;
}
if (*p == ')') {
while (op_stack.top() != '(') {
double b = num_stack.top();
num_stack.pop();
double a = num_stack.top();
num_stack.pop();
char op = op_stack.top();
op_stack.pop();
double res = deal_op(a, b, op);
num_stack.push(res);
}
op_stack.pop();
p++;
continue;
}
char op = *p;
while (!op_stack.empty() && get_priority(op) <= get_priority(op_stack.top())) {
double b = num_stack.top();
num_stack.pop();
double a = num_stack.top();
num_stack.pop();
char top_op = op_stack.top();
op_stack.pop();
double res = deal_op(a, b, top_op);
num_stack.push(res);
}
op_stack.push(op);
p++;
}
while (!op_stack.empty()) {
double b = num_stack.top();
num_stack.pop();
double a = num_stack.top();
num_stack.pop();
char op = op_stack.top();
op_stack.pop();
double res = deal_op(a, b, op);
num_stack.push(res);
}
return num_stack.top();
}
int main() {
char exp[100];
cin.getline(exp, 100);
double res = deal_exp(exp);
cout << res << endl;
return 0;
}
```
该算法的基本思路是维护两个栈,一个存储数字,一个存储运算符。从左到右扫描表达式,如果遇到数字,就把它压入数字栈中;如果遇到运算符,则将该运算符与运算符栈的栈顶元素进行比较,如果优先级大于等于栈顶元素,则将该运算符压入运算符栈中;否则,将运算符栈中的元素弹出,将数字栈中的两个数字弹出,进行运算,并将结果压入数字栈中。当表达式扫描完毕后,将运算符栈中的元素依次弹出,再将数字栈中的两个数字弹出,进行运算,并将结果压入数字栈中,最终数字栈中的元素就是表达式的值。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)