C++ 中缀表达式求值算法实现

本文将介绍如何使用 C++ 语言实现一个中缀表达式求值算法，并附带完整的代码示例。

算法步骤

中缀表达式求值算法主要分为以下步骤：

初始化：创建一个运算符栈 OPTR 和一个操作数栈 OPND，并将 '#' 符号压入 OPTR 栈顶，表示表达式结束。
读取表达式：从输入流中读取中缀表达式，逐个字符进行处理。
判断字符类型：
- 如果当前字符是操作数，将其转换为浮点数并压入 OPND 栈。
- 如果当前字符是运算符，则根据其与 OPTR 栈顶运算符的优先级进行比较，并执行以下操作：
  - 如果当前运算符的优先级低于或等于 OPTR 栈顶运算符，则将 OPTR 栈顶运算符弹出，并将两个 OPND 栈顶操作数出栈并进行运算，将运算结果压入 OPND 栈。
  - 如果当前运算符的优先级高于 OPTR 栈顶运算符，则将当前运算符压入 OPTR 栈。
循环处理：重复步骤 2 和 3，直到表达式结束。
返回结果：最后 OPND 栈顶元素即为表达式的值。

代码示例

#include 'SeqStack.cpp'
#include <iostream>
#include <stdlib.h>
#include <string.h>
#define OperaterSetSize  7
#include <cstdlib> 
using namespace std;
char OperaterSet[OperaterSetSize] = {'+', '-', '*', '/', '(', ')', '#' };
unsigned char Prior[7][7] = {     
   '>', '>', '<', '<', '<', '>', '>',
   '>', '>', '<', '<', '<', '>', '>',
   '>', '>', '>', '>', '<', '>', '>',
   '>', '>', '>', '>', '<', '>', '>', 
   '<', '<', '<', '<', '<', '=', ' ',
   '>', '>', '>', '>', ' ', '>', '>',
   '<', '<', '<', '<', '<', ' ', '=' 
}; 
int IsOperator(char c) {
	 int flag = 0;
	 for(int i = 0; i < OperaterSetSize; i++) {
		 if(c == OperaterSet[i]) {
			 flag = 1;
			 break;
		 }
	 }
	 return flag;
}
int ReturnOpOrd(char oper) {
   	for(int i = 0; i < OperaterSetSize; i++) {
   		 if (oper == OperaterSet[i]) {
      		 return i;
	  	}
   	}
   	return -1;
}
char Priority(char c1, char c2) {
	int i,j;
	i = ReturnOpOrd(c1);
	j = ReturnOpOrd(c2);
	return Prior[i][j];
}
double Operate(double a, unsigned char c, double b) {
	switch(c) {
		case '+':
			return a + b;
		case '-':
			return a - b;
		case '*':
			return a * b;
		case '/':
			return a / b;
		default:
			return 0;
	}
}
float EvaluateInExpression() {
	SeqStack<char> OPTR; 
   	SeqStack<float> OPND; 
   	char tmp[20]; 
   	float data, a, b;
   	char oper, c, cton[2];
   	OPTR.Push('#');
   	strcpy(tmp, '�');
   	c = getchar();
   	while (c != '#' || OPTR.GetTop() != '#') {
		if(!IsOperator(c)) {
        		cton[0] = c;
        		cton[1] = '�'; 
        		strcat(tmp, cton); 
        		c = getchar();
        		if(IsOperator(c)) {
        			data = (float)atof(tmp);
            		OPND.Push(data);
            		strcpy(tmp, '�');
        		}
    	}
   		else {
        		switch(Priority(OPTR.GetTop(), c)) { 
            		case '<': 
                		OPTR.Push(c);
                 		c = getchar();
                 		break;
            		case '=': 
                 		OPTR.Pop();   
                 		c = getchar();
                 		break;
            		case '>': 
            			oper = OPTR.Pop();
            			b = OPND.Pop();
            			a = OPND.Pop();
                 		OPND.Push(Operate(a, oper, b)); 
                 		break;
                	default:
                		break;
         	}
        }
    }
   	return OPND.GetTop();
}

int main() {
	 system('color F0');  
    cout<<'项目实现人：顾文婧'<<endl; 
	cout<<'请输入中缀表达式：（以'#'结束）：'<<endl;
	cout<<EvaluateInExpression()<<endl;
}

难点及解决方法

如何判断一个字符是否为运算符？

可以定义一个函数 IsOperator(char c) 来判断一个字符是否为运算符。在该函数中，遍历操作符集合，如果字符与集合中的任意一个字符相等，则返回 1，表示是运算符，否则返回 0，表示不是运算符。
如何确定两个运算符的优先级？

可以定义一个二维数组 Prior 来表示两个运算符的优先级。在函数 Priority(char c1, char c2) 中，根据运算符 c1 和 c2 在 OperaterSet 中的位置，通过 Prior 数组来确定它们的优先级。
如何进行运算符的入栈和出栈操作？

可以使用两个栈来实现运算符的入栈和出栈操作。一个栈用于存储运算符（OPTR），另一个栈用于存储操作数（OPND）。在遍历输入字符串时，根据运算符的优先级进行入栈和出栈操作。
如何将输入的字符串转化为数字进行运算？

可以使用 atof 函数将字符串转化为浮点数进行运算。在遍历输入字符串时，遇到数字字符时，将其加入一个临时字符串 tmp 中，直到遇到下一个运算符字符。然后使用 atof 函数将 tmp 转化为浮点数，并将其入栈。
如何处理多位数的情况？

可以在遍历输入字符串时，使用一个临时字符串 tmp 来存储数字字符。当遇到运算符字符时，将 tmp 转化为浮点数，并将其入栈。然后将 tmp 清空，准备下一个数字字符的存储。
如何处理括号的情况？

在遍历输入字符串时，遇到左括号时，将其入栈。遇到右括号时，将栈顶的运算符出栈，直到遇到左括号为止。然后将左括号和右括号都丢弃，继续处理下一个字符。

总结

本文介绍了使用 C++ 语言实现中缀表达式求值算法的步骤和代码示例，并分析了代码实现过程中可能遇到的难点和解决方法。该算法是计算机科学中一个重要的基础算法，它在编译器、解释器等方面都有着广泛的应用。