利用栈来实现算术表达式求值的算法。定义 函数 In(c):判断 c 是否为运算符和函数 Precede(t1,t2):判断运算符 t1 和 t2 的优先级还有 函数 Operate(a,theta,b):对 a 和 b 进行二元运算 theta。
时间: 2023-04-10 11:00:30 浏览: 202
可以回答这个问题。算术表达式求值的算法可以通过利用栈来实现。具体步骤如下:
1. 定义两个栈,一个用来存储操作数,一个用来存储运算符和括号。
2. 从左到右扫描表达式,遇到操作数就直接入操作数栈,遇到运算符或括号则进行如下操作:
a. 如果运算符或括号栈为空,或者栈顶元素为左括号,则直接入栈。
b. 如果遇到右括号,则将运算符栈中的元素依次弹出,直到遇到左括号为止,并将左括号弹出。
c. 如果遇到运算符,则比较其与栈顶运算符的优先级,如果优先级高于栈顶运算符,则直接入栈,否则将栈顶运算符弹出,并将操作数栈中的两个操作数弹出,进行二元运算,并将结果入操作数栈,直到优先级高于栈顶运算符或者栈为空为止,然后将当前运算符入栈。
3. 当表达式扫描完毕后,如果运算符栈中还有元素,则依次弹出运算符,并将操作数栈中的两个操作数弹出,进行二元运算,并将结果入操作数栈,直到运算符栈为空为止。
4. 最终操作数栈中只剩下一个元素,即为表达式的值。
函数 In(c):判断 c 是否为运算符和函数
可以使用以下代码实现:
bool In(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')' || c == '^')
return true;
else
return false;
}
函数 Precede(t1,t2):判断运算符 t1 和 t2 的优先级
可以使用以下代码实现:
int Precede(char t1, char t2)
{
int p1, p2;
switch (t1)
{
case '+':
case '-':
p1 = 1;
break;
case '*':
case '/':
p1 = 2;
break;
case '^':
p1 = 3;
break;
case '(':
p1 = 4;
break;
case ')':
p1 = 0;
break;
}
switch (t2)
{
case '+':
case '-':
p2 = 1;
break;
case '*':
case '/':
p2 = 2;
break;
case '^':
p2 = 3;
break;
case '(':
p2 = 0;
break;
case ')':
p2 = 4;
break;
}
if (p1 == p2)
return 0;
else if (p1 < p2)
return -1;
else
return 1;
}
函数 Operate(a,theta,b):对 a 和 b 进行二元运算 theta
可以使用以下代码实现:
double Operate(double a, char theta, double b)
{
switch (theta)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return pow(a, b);
}
}
阅读全文