算术表达式求值的代码
时间: 2024-05-13 11:11:45 浏览: 16
算术表达式求值是指将一个数学表达式计算出结果的过程,比如输入字符串"3+4*2-1",我们需要计算出它的结果9。算术表达式求值的代码可以分为两个部分:中缀表达式转后缀表达式和后缀表达式求值。
中缀表达式转后缀表达式的过程可以使用栈来实现。具体步骤如下:
1. 初始化一个操作符栈和一个输出队列。
2. 从左到右扫描中缀表达式,如果是数字,直接输出到队列中。
3. 如果是操作符,判断其与操作符栈栈顶元素的优先级,如果优先级低于或等于栈顶元素,则弹出栈顶元素并输出到队列中,重复此步骤直到优先级高于栈顶元素或栈为空,然后将该操作符入栈。
4. 如果是左括号"(",则直接入栈。
5. 如果是右括号")",则依次弹出栈顶元素并输出到队列中,直到遇到左括号为止,左右括号均不输出。
6. 重复步骤2至5直到扫描完毕,将栈中剩余的操作符依次弹出并输出到队列中。
得到后缀表达式后,可以使用栈来进行后缀表达式的求值。具体步骤如下:
1. 初始化一个操作数栈。
2. 从左到右扫描后缀表达式,如果是数字,将其入栈。
3. 如果是操作符,则从操作数栈中弹出两个元素进行计算,并将计算结果入栈。
4. 重复步骤2至3直到扫描完毕,此时操作数栈中只剩下一个元素,即为最终结果。
以下是一个简单的C++代码示例:
```c++
#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;
int priority(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
return 0;
}
queue<string> infixToSuffix(string infix) {
stack<char> opStack;
queue<string> suffix;
int i = 0;
while (i < infix.length()) {
if (isdigit(infix[i])) {
string numStr;
while (i < infix.length() && isdigit(infix[i])) {
numStr += infix[i];
i++;
}
suffix.push(numStr);
}
else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
while (!opStack.empty() && priority(opStack.top()) >= priority(infix[i])) {
suffix.push(string(1, opStack.top()));
opStack.pop();
}
opStack.push(infix[i]);
i++;
}
else if (infix[i] == '(') {
opStack.push(infix[i]);
i++;
}
else if (infix[i] == ')') {
while (opStack.top() != '(') {
suffix.push(string(1, opStack.top()));
opStack.pop();
}
opStack.pop();
i++;
}
else {
i++;
}
}
while (!opStack.empty()) {
suffix.push(string(1, opStack.top()));
opStack.pop();
}
return suffix;
}
double evaluateSuffix(queue<string> suffix) {
stack<double> numStack;
while (!suffix.empty()) {
string s = suffix.front();
suffix.pop();
if (isdigit(s)) {
numStack.push(stod(s));
}
else {
double num2 = numStack.top();
numStack.pop();
double num1 = numStack.top();
numStack.pop();
if (s == '+') numStack.push(num1 + num2);
else if (s == '-') numStack.push(num1 - num2);
else if (s == '*') numStack.push(num1 * num2);
else if (s == '/') numStack.push(num1 / num2);
}
}
return numStack.top();
}
int main() {
string infix = "3+4*2-1";
queue<string> suffix = infixToSuffix(infix);
double result = evaluateSuffix(suffix);
cout << result << endl;
return 0;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)
![](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)