栈及其应用之表达式求值
任务描述
本关任务：编写从键盘输入一个算术表达式并输出它的结果的程序。
相关知识
为了完成本关任务，你需要掌握：栈的基本操作的实现，并能灵活运用栈特性，综合运用程序设计、算法分析等知识解决实际问题。
表达式作为一个串存储，如表达式“32-(4+21)”,其求值过程为：自左向右扫描表达式，当扫描到32时不能马上计算，因后面可能还有更高的运算，正确的处理过程是：
需要两个栈：对象栈s_num和算符栈s_opt;自左至右扫描表达式, 若当前字符是运算对象，入s_num栈;对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从s_num栈出栈两个数，从栈s_opt出栈一运算符进行运算，并将其运算结果入s_num栈，继续处理当前字符，直到遇到结束符。 *
编程要求
根据提示，在右侧编辑器补充代码，计算并输出运算表达式的结果。
测试说明
平台会对你编写的代码进行测试：
测试输入：3*（5-2）；
预期输出：
9
开始你的任务吧，祝你成功！
原来写了一个，可以用一下 支持加减乘除 指数，浮点数，是以回车换行结束，中间不能有空格
测试如下
./htest
32-(4+21)
7
./htest
3*(5-2)*3
27
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX_SIZE 100
#define EXP_DATA_INVALID 0
#define EXP_DATA_DOUBLE 1
#define EXP_DATA_INT 2
#define EXP_DATA_OP 3
char legel_letter[] = "1234567890.[]()+-*/^ ";
char legel_op[] = "[(+-*/^";
typedef struct _exp_data {
union {
double d_d;
int i_d;
char op;
} u;
int type;
} exp_data;
typedef struct _stack {
exp_data *data;
int top;
int size;
} stack;
void init(stack *s)
{
s->data = (exp_data *)malloc(sizeof(exp_data) * MAX_SIZE);
s->size = MAX_SIZE;
s->top = -1;
}
int empty(stack *s)
{
return s->top == -1;
}
exp_data top(stack *s)
{
exp_data invalid;
invalid.type = EXP_DATA_INVALID;
if (empty(s))
return invalid;
return s->data[s->top];
}
int push(stack *s, exp_data val)
{
if (s == NULL || s->top + 1 == s->size)
return 0;
s->top += 1;
s->data[s->top] = val;
return 1;
}
int pop(stack *s)
{
if (s == NULL || empty(s))
return 0;
s->top -= 1;
return 1;
}
int judge_oper(char *str, char letter)
{
char sub[1] = {0};
char *p;
sub[0] = letter;
sub[1] = '\0';
if(( p = strstr(str, sub)) == NULL) return 0;
else return 1;
}
int get_op_number(char *str, exp_data *val)
{
int i = 0;
int flag_d_d = 0;
char d_d_i[100] = {0};
for (; (str[i]>= '0' && str[i] <= '9') || str[i] == '.'; i++) {
if (str[i] == '.') flag_d_d = 1;
d_d_i[i] = str[i];
}
if (i > 0) {
if (flag_d_d) {
val->u.d_d = strtod (d_d_i, NULL);
val->type = EXP_DATA_DOUBLE;
} else {
val->u.i_d = strtod (d_d_i, NULL);
val->type = EXP_DATA_INT;
}
}
return i;
}
void do_op_number(stack *s, exp_data val)
{
exp_data top_1;
exp_data top_2;
char op;
int flag_d_oper1 = 0;
int flag_d_oper2 = 0;
double d_d;
if(empty(s)) {push(s, val); return;}
top_1 = top(s);
if (top_1.type != EXP_DATA_OP) { printf("error_1\n"); return; }
op = top_1.u.op;
if (op == '(' || op == '[') { push(s, val); return;}
pop(s);
top_2 = top(s);
if (top_2.type == EXP_DATA_INVALID || top_2.type == EXP_DATA_OP) { printf("error_1\n"); return;}
pop(s);
if (top_2.type == EXP_DATA_DOUBLE) flag_d_oper2 = 1;
if (val.type == EXP_DATA_DOUBLE) flag_d_oper1 = 1;
switch(op) {
case '+':
d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) + (flag_d_oper1?val.u.d_d : val.u.i_d);
break;
case '-':
d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) - (flag_d_oper1?val.u.d_d : val.u.i_d);
break;
case '*':
d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) * (flag_d_oper1?val.u.d_d : val.u.i_d);
break;
case '/':
if ((flag_d_oper1?val.u.d_d : val.u.i_d) == 0) { printf("error_3\n"); return;}
d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) / (flag_d_oper1?val.u.d_d : val.u.i_d);
break;
case '^':
d_d = pow((flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) , (flag_d_oper1?val.u.d_d : val.u.i_d));
break;
}
if(flag_d_oper1 || flag_d_oper2) {
val.type = EXP_DATA_DOUBLE;
val.u.d_d = d_d;
push(s, val);
} else {
val.type = EXP_DATA_INT;
val.u.i_d = (int)d_d;
push(s, val);
}
}
void do_op_brackets(stack *s, char letter)
{
exp_data top_1;
exp_data top_2;
top_1 = top(s);
pop(s);
//do (1+2)
do_op_number(s, top_1);
//do remove (1) and restore 1 to stack
top_1 = top(s);
pop(s);
top_2 = top(s);
pop(s);
push(s, top_1);
if ( letter == ')' ) {
if (top_2.type != EXP_DATA_OP || top_2.u.op != '(') {
printf("error_3\n");
return ;
}
}
if ( letter == ']' ) {
if (top_2.type != EXP_DATA_OP || top_2.u.op != '[') {
printf("error_3\n");
return ;
}
}
}
int need_compute(char cur_op, char pre_op)
{
//if (pre_op == '(' || pre_op == '[') return 0;
if (cur_op == '+' || cur_op == '-') return 1;
if (cur_op == '*' || cur_op == '/') {
if (pre_op == '+' || pre_op == '-') return 0;
else return 1;
}
if (cur_op == '^') return 0;
return 1;
}
void do_push_op_brackets(stack *s, char letter)
{
exp_data val;
val.type = EXP_DATA_OP;
val.u.op = letter;
exp_data top_1, top_2, top_3;
if (empty(s) || letter == '(' || letter == '[' || letter == '^') {
if (push(s, val) == 0) { printf("push brackets error\n"); }
return;
}
while(!empty(s)) {
top_1 = top(s);
pop(s);
if(empty(s)) { push(s, top_1); push(s, val); return;}
top_2 = top(s);
if(top_2.type == EXP_DATA_OP && (top_2.u.op == '(' || top_2.u.op == '[')) {
push(s, top_1); push(s, val); return;
}
pop(s);
if(empty(s)) { push(s, top_2); push(s, top_1); push(s, val); return;}
top_3 = top(s);
pop(s);
if (top_2.type != EXP_DATA_OP) { printf("error_3\n"); return; }
if (need_compute(letter, top_2.u.op)) {
push(s, top_3); push(s, top_2);
do_op_number(s, top_1);
} else {
push(s, top_3); push(s, top_2); push(s, top_1);
push(s, val);
return;
}
}
push(s, val);
}
void do_compute(char *exp)
{
stack s;
exp_data val;
int i = 0, jump = 0;
char letter;
init(&s);
letter = exp[i];
while(letter != '\0') {
if (judge_oper(legel_letter, letter) == 0) { printf("error_0\n"); break;}
if (judge_oper(legel_op, letter)) { do_push_op_brackets(&s, letter); }
if (letter == ')' || letter == ']') { do_op_brackets(&s, letter); }
if (letter == '.' && (i == 0 || exp[i-1] > '9' || exp[i-1] < '0')) {printf("error_00\n"); break;}
if ((letter >= '0' && letter <= '9') || letter == '.') {
jump = get_op_number(&exp[i], &val);
if (!jump) { printf("error_000\n"); break;}
push(&s, val);
i+=jump;
jump = 0;
} else i++;
letter = exp[i];
}
if(empty(&s)) { printf("error_30\n"); goto err; }
exp_data top_1, top_2;
while(!empty(&s) && s.top >= 2) {
top_1 = top(&s);
pop(&s);
do_op_number(&s, top_1);
}
//do last result
top_1 = top(&s);
pop(&s);
if (!empty(&s)) { printf("error_300\n"); goto err; }
if (top_1.type == EXP_DATA_OP) printf("error_3000\n");
else {
if (top_1.type == EXP_DATA_DOUBLE) printf("%lf\n", top_1.u.d_d);
else printf("%d\n", top_1.u.i_d);
}
err:
if (s.data) free(s.data);
}
int main()
{
char exp[100];
scanf("%s", exp);
do_compute(exp);
return 0;
}
#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
stack<char>OPTR;
stack<double>OPND;
typedef struct {//因为在输入表达式时是一个一个的输入字符，而操作数若长度大于2则无法正确得到操作数，因此该结构是用来存储一个完整的字符数，便于在CharTOInt()中将其转换为数字
char data[10];
int length;
}haha;
bool In(char ch)//判断输入的是不是运算符，若是则返回true
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')'||ch=='#')
{
return true;
}
else return false;
}
char Precede(char x, char y)//运算符优先级的判断
{
int ang[2];
char opnd[2] = { x,y };
char aa[7][7] = {
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=',' '},
{'>','>','>','>',' ','>','>'},
{'<','<','<','<','<',' ','='}
};
for (int z = 0; z < 2; z++)
{
switch (opnd[z])
{
case '+':ang[z] = 0;
break;
case '-':ang[z] = 1;
break;
case '*':ang[z] = 2;
break;
case '/':ang[z] = 3;
break;
case '(':ang[z] = 4;
break;
case ')':ang[z] = 5;
break;
case '#':ang[z] = 6;
break;
}
}
return aa[ang[0]][ang[1]];
}
double Operate(double a, char theta, double b)//加减乘除运算
{
double result;
switch (theta)
{
case '+': result=a + b;
break;
case '-':result= a - b;
break;
case '*':result= a * b;
break;
case '/':result= a / b;
break;
}
return result ;
}
double charTOint(haha cunchu)//将字符数字转换成一个完整的数字型数字
{
int point=0;//用来判断是否有小数点以及小数点的位置
double result=0;
for (int i = 0; i < cunchu.length; i++)//先找出小数点的位置
{
if (cunchu.data[i] == '.')
break;
++point;
}
for (int i=0,j = 0; i < cunchu.length; i++)//根据结构中的length以及小数点位置可以正确转换数字
{
if (i != point)//小数点不放入计算
{
result += (cunchu.data[i] - '0')*pow(10, point - j - 1);
j++;
}
}
return result;
}
double EvaluateExpression()//最关键的方法
{
bool flag = true;//用来判断是否输入一个数字完毕，输入完毕则转化为数字型，存入栈中
haha cunchu;//用来记录每个数字字符，然后转换为数字计算
OPTR.push('#');//将表达式起始符压入栈中，用于判断是否该结束循环
char ch;
int i=0;
char theta;//记录弹出来的运算符
double a, b;//记录弹出来的操作数
cout<<"请输入正确的表达式，以'#'结束"<<endl;
cin >> ch;
cunchu.length = 0;
while (ch != '#' || OPTR.top() != '#')//就算ch=='#'也不一定停止循环，因为OPTR中可能还有加减乘除需要运算
{
if (!In(ch))
{
cunchu.data[i] = ch;
++i;
++cunchu.length;
flag = true;
cin >> ch;
}
else {
if (flag)//这判断非常重要，是操作数正确进栈关键方法。思路：即当输入运算符时，表明运算符的前一个操作数已经输入完毕，此时可以将结构存储的数字字符转换成double型，并将数字进入OPND栈
{
OPND.push(charTOint(cunchu));//字符转换数字
cunchu.length = 0; i = 0;//所有回到初始化，用以记录下一个数字
flag = false;//操作数进栈成功后必须将flag取反，因为当操作数进栈后，它在switch中，若进行case '>'时，此时的ch操作符是还没进栈的，ch还需再次进入while循环，判断ch与OPTR栈顶操作符比较优先级，
//再决定ch的情况。正因为ch还需进入while循环，所以在此之前需将flag=false，否则flag=true,又会执行OPND.push(charTOint(cunchu)),这时是将数字0进栈，将会导致运算出错
}
switch (Precede(OPTR.top(), ch))
{
case '>': { theta = OPTR.top();OPTR.pop(); //如果栈顶运算符优先级较大，则取OPND栈顶两个数以及OPTR栈顶运算符进行运算，结果再入栈
b= OPND.top(); OPND.pop();
a= OPND.top(); OPND.pop();
OPND.push(Operate(a, theta, b));//此处不用输入ch，是因为原值还没入栈，其优先级比较小，仍要跟下一个栈顶比较
break;
}
case '<': {
OPTR.push(ch);
cin >> ch;
break;
}
case '=': {
OPTR.pop();
cin >> ch;
break;
}
}
}
}
return OPND.top();
}
int main()
{
cout<<"结果:"<<EvaluateExpression();
}
望采纳:
#include<bits/stdc++.h>
using namespace std;
#define max 1000
int calculate(char * s)
{
char stack1[max],ch;
int stack2[max];
int top1=-1,top2=-1,i,a,b,j,flag=0,sum=0;
for(i=0;s[i]!='\0';i++)
{
if(s[i]=='(')
stack1[++top1]=s[i];
else if(s[i]=='+'||s[i]=='-')
{
flag=1;//进行过运算
if(top1!=-1&&(stack1[top1]=='+'||stack1[top1]=='-'))
{
ch=stack1[top1--];
b=stack2[top2--];
if(top2!=-1)
a=stack2[top2--];
else //+/-为正负号
a=0;
if(ch=='+')
stack2[++top2]=a+b;
else
stack2[++top2]=a-b;
}
stack1[++top1]=s[i];
}
else if(s[i]==')')
{
while(stack1[top1]!='(')
{
ch=stack1[top1--];
b=stack2[top2--];
a=stack2[top2--];
if(ch=='+')
stack2[++top2]=a+b;
else
stack2[++top2]=a-b;
}
--top1;
}
else if(s[i]>='0'&&s[i]<='9')//转换为整数再进栈
{
if(i>0&&(s[i-1]>='0'&&s[i-1]<='9'))//十位数以上
{
j=stack2[top2--];
j=j*10+(s[i]-'0');
stack2[++top2]=j;
}
else
stack2[++top2]=s[i]-'0';
}
}
while(top1>-1)
{
ch=stack1[top1--];
b=stack2[top2--];
if(top2!=-1)
a=stack2[top2--];
else
a=0;
if(ch=='+')
stack2[++top2]=a+b;
else
stack2[++top2]=a-b;
}
for(i=0;flag==0&&i<=top2;i++)//未进行过运算，纯数字处理
sum=sum*10+(stack2[i]);
if(flag&&top2>-1)
sum=stack2[top2--];
return sum;
}
int main(){
while(1){
char *a;
scanf("%s",a);
printf("%d\n",calculate(a));
}
}
#include<iostream>
using namespace std;
const char oper[7] = { '+', '-', '*', '/', '(', ')', '#' };
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char SElemType;
typedef int Status;
typedef struct SNode {
int data;
struct SNode *next;
} SNode, *LinkStack;
Status InitStack(LinkStack &S) {
S = NULL;
return OK;
}
bool StackEmpty(LinkStack S) {
if (!S)
return true;
return false;
}
Status Push(LinkStack &S, SElemType e) {
SNode *p = new SNode;
if (!p) {
return OVERFLOW;
}
p->data = e;
p->next = S;
S = p;
return OK;
}
Status Pop(LinkStack &S, SElemType &e) {
SNode *p;
if (!S)
return ERROR;
e = S->data;
p = S;
S = S->next;
delete p;
return OK;
}
Status GetTop(LinkStack &S) {
if (!S)
return ERROR;
return S->data;
}
bool In(char ch) {//判断ch是否为运算符
for (int i = 0; i < 7; i++) {
if (ch == oper[i]) {
return true;
}
}
return false;
}
char Precede(char theta1, char theta2) {//判断运算符优先级
if ((theta1 == '(' && theta2 == ')') || (theta1 == '#' && theta2 == '#')) {
return '=';
} else if (theta1 == '(' || theta1 == '#' || theta2 == '(' || (theta1
== '+' || theta1 == '-') && (theta2 == '*' || theta2 == '/')) {
return '<';
} else
return '>';
}
char Operate(char first, char theta, char second) {//计算两数运算结果
switch (theta) {
case '+':
return (first - '0') + (second - '0') + 48;
case '-':
return (first - '0') - (second - '0') + 48;
case '*':
return (first - '0') * (second - '0') + 48;
case '/':
return (first - '0') / (second - '0') + 48;
}
return 0;
}
//算法3.22 表达式求值
char EvaluateExpression() {//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈
LinkStack OPTR, OPND;
char ch, theta, a, b, x, top;
InitStack(OPND); //初始化OPND栈
InitStack(OPTR); //初始化OPTR栈
Push(OPTR, '#'); //将表达式起始符“#”压入OPTR栈
cin >> ch;
while (ch != '#' || (GetTop(OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
{
if (!In(ch)) {
Push(OPND, ch);
cin >> ch;
} //ch不是运算符则进OPND栈
else
switch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级
{
case '<':
Push(OPTR, ch);
cin >> ch; //当前字符ch压入OPTR栈，读入下一字符ch
break;
case '>':
Pop(OPTR, theta); //弹出OPTR栈顶的运算符
Pop(OPND, b);
Pop(OPND, a); //弹出OPND栈顶的两个运算数
Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈
break;
case '=': //OPTR的栈顶元素是“(”且ch是“)”
Pop(OPTR, x);
cin >> ch; //弹出OPTR栈顶的“(”，读入下一字符ch
break;
} //switch
} //while
return GetTop(OPND); //OPND栈顶元素即为表达式求值结果
}
主函数代码如下：
#include"main.h"
int menu() {
int c;
cout << "0-9以内的多项式计算" << endl;
cout << "1.计算" << endl;
cout << "0.退出\n" << endl;
cout << "选择：";
cin >> c;
return c;
}
void main() {
while (1) {
switch (menu()) {
case 1: {
cout << "请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）：" << endl;
char res = EvaluateExpression();//算法3.22 表达式求值
cout << "计算结果为: " << res - 48 << endl << endl;
}
break;
case 0:
cout << "退出成功\n" << endl;
exit(0);
default:
break;
}
}
}
来自网络https://www.cnblogs.com/dzwj/p/15659484.html#:~:text=%E6%A0%88%E5%AE%9E%E7%8E%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC,%E4%BD%BF%E7%94%A8%E9%94%AE%E7%9B%98%E8%BE%93%E5%85%A5%E6%95%B0%E5%AD%A6%E8%A1%A8%E8%BE%BE%E5%BC%8F%EF%BC%88%E5%90%AB%E6%95%B0%E5%AD%97%EF%BC%8C%E5%9B%9B%E7%A7%8D%E8%BF%90%E7%AE%97%E7%AC%A6%2B%E3%80%81-%E3%80%81%E3%80%81%2F%E5%92%8C%E5%B0%8F%E6%8B%AC%E5%8F%B7%EF%BC%8C%E5%85%B6%E4%B8%AD%E8%BF%90%E7%AE%97%E6%95%B0%E9%83%BD%E6%98%AF%E4%B8%80%E4%BD%8D%E6%95%B0%20%280%EF%BD%9E9%29%EF%BC%89%EF%BC%8C%E5%B0%86%E6%95%B0%E5%AD%A6%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%BD%AC%E5%8C%96%E6%88%90%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E8%BE%93%E5%87%BA%EF%BC%8C%E5%88%A9%E7%94%A8%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%9A%84%E5%80%BC%E5%B9%B6%E8%BE%93%E5%87%BA%E3%80%82
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>
#include <math.h>
using namespace std;
stack<int> MoveIn;
stack<char> CharStack;
string fixStr = "";
void IntoPost(string inStr);
bool isPush(char pre, char late);
void Calculate(char np);
void CalFix();
void pushChar(char np);
string format(string inStr) { //解决（-1+2）负数报错问题
for (int i = 0; i < inStr.length(); i++) //即在 -1 前面加一个0 变成 0-1 即可
if (inStr[i] == '-')
if (i == 0)
inStr.insert(0, 1, '0');
else if (inStr[i - 1] == '(')
inStr.insert(i, 1, '0');
return inStr;
}
int main(){
string inStr;
getline(cin, inStr);
//使用getline 解决字符串录入遇空格结束的问题 类似 （ a + b ） 只写入了 （ 的
inStr = format(inStr);
int i=0;
int K_num=0;
int K_1=0;
int K_2=0;
while(inStr[i]!='\0')
{
if(inStr[i]=='('||inStr[i]==')')
{
K_num++;
}
if(inStr[i]=='+'||inStr[i]=='-'||inStr[i]=='*'||inStr[i]=='/')
{
if(inStr[i+1]=='+'||inStr[i+1]=='-'||inStr[i+1]=='*'||inStr[i+1]=='/')
{
K_1=1;
printf("ERROR:表达式缺操作数");
}
}
i++;
}
if(K_num%2!=0)
{
K_2=1;
printf("ERROR:缺少括号");
}
if((K_1==0)&&(K_2==0))
{
IntoPost(inStr);
//cout<<fixStr<<endl;
CalFix();
}
return 0;
}
void IntoPost(string inStr) { //前缀转后缀
for (int i = 0; i < inStr.length(); i++) {
switch (inStr[i]) {
case ' ': break;
case '+':pushChar('+'); break;
case '(':CharStack.push('('); break;//遇前括号直接入栈
case ')': //遇后括号弹出所有至上一个括号
while (CharStack.top() != '(') {
fixStr += CharStack.top();
CharStack.pop();
}
CharStack.pop();
break;
case '/':pushChar('/'); break;
case '*':pushChar('*'); break;
case '-':pushChar('-'); break;
case '^':pushChar('^'); break;
default:
fixStr += inStr[i]; break; //数字直接输出
}
}
while (!CharStack.empty()) { //整式尾部时弹出所有站内符号
fixStr += CharStack.top();
CharStack.pop();
}
}
void pushChar(char np) { //运算符出栈
if (!CharStack.empty()){
while (!CharStack.empty() && isPush(CharStack.top(), np)) {
fixStr += CharStack.top(); //判断优先级
CharStack.pop();
}
CharStack.push(np);
}
else
CharStack.push(np);
}
bool isPush(char pre, char late) { //优先级比较
if (late == '^')
if (pre == '^') return true;
else return false;
if (late == '*' || late == '/')
if (pre == '^' || pre == '*' || pre == '/') return true;
else return false;
if (late == '+' || late == '-')
if (pre == '(') return false;
else return true;
return false;
}
void CalFix() { //后缀表达式计算
for (int i = 0; i < fixStr.length(); i++) {
switch (fixStr[i]) {
case '+':Calculate('+'); break;
case '/':Calculate('/'); break;
case '*':Calculate('*'); break;
case '-':Calculate('-'); break;
case '^':Calculate('^'); break;
case ' ': break;
default:
int a;
a = (int)(fixStr[i] - 48);
MoveIn.push(a);
break;
}
}
cout << MoveIn.top();
}
void Calculate(char np) { //弹出两个栈内数运算后再压进栈
int pre, late;
late = MoveIn.top();
MoveIn.pop();
pre = MoveIn.top();
MoveIn.pop();
switch (np) {
case '+':MoveIn.push(pre + late); break;
case '/':MoveIn.push(pre / late); break;
case '*':MoveIn.push(pre * late); break;
case '-':MoveIn.push(pre - late); break;
case '^':MoveIn.push(pow(pre,late)); break;
default:
break;
}
}
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7591363
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>
#include <math.h>
using namespace std;
stack<int> MoveIn;
stack<char> CharStack;
string fixStr = "";
void IntoPost(string inStr);
bool isPush(char pre, char late);
void Calculate(char np);
void CalFix();
void pushChar(char np);
string format(string inStr) { //解决（-1+2）负数报错问题
for (int i = 0; i < inStr.length(); i++) //即在 -1 前面加一个0 变成 0-1 即可
if (inStr[i] == '-')
if (i == 0)
inStr.insert(0, 1, '0');
else if (inStr[i - 1] == '(')
inStr.insert(i, 1, '0');
return inStr;
}
int main(){
string inStr;
getline(cin, inStr);
//使用getline 解决字符串录入遇空格结束的问题 类似 （ a + b ） 只写入了 （ 的
inStr = format(inStr);
int i=0;
int K_num=0;
int K_1=0;
int K_2=0;
while(inStr[i]!='\0')
{
if(inStr[i]=='('||inStr[i]==')')
{
K_num++;
}
if(inStr[i]=='+'||inStr[i]=='-'||inStr[i]=='*'||inStr[i]=='/')
{
if(inStr[i+1]=='+'||inStr[i+1]=='-'||inStr[i+1]=='*'||inStr[i+1]=='/')
{
K_1=1;
printf("ERROR:表达式缺操作数");
}
}
i++;
}
if(K_num%2!=0)
{
K_2=1;
printf("ERROR:缺少括号");
}
if((K_1==0)&&(K_2==0))
{
IntoPost(inStr);
//cout<<fixStr<<endl;
CalFix();
}
return 0;
}
void IntoPost(string inStr) { //前缀转后缀
for (int i = 0; i < inStr.length(); i++) {
switch (inStr[i]) {
case ' ': break;
case '+':pushChar('+'); break;
case '(':CharStack.push('('); break;//遇前括号直接入栈
case ')': //遇后括号弹出所有至上一个括号
while (CharStack.top() != '(') {
fixStr += CharStack.top();
CharStack.pop();
}
CharStack.pop();
break;
case '/':pushChar('/'); break;
case '*':pushChar('*'); break;
case '-':pushChar('-'); break;
case '^':pushChar('^'); break;
default:
fixStr += inStr[i]; break; //数字直接输出
}
}
while (!CharStack.empty()) { //整式尾部时弹出所有站内符号
fixStr += CharStack.top();
CharStack.pop();
}
}
void pushChar(char np) { //运算符出栈
if (!CharStack.empty()){
while (!CharStack.empty() && isPush(CharStack.top(), np)) {
fixStr += CharStack.top(); //判断优先级
CharStack.pop();
}
CharStack.push(np);
}
else
CharStack.push(np);
}
bool isPush(char pre, char late) { //优先级比较
if (late == '^')
if (pre == '^') return true;
else return false;
if (late == '*' || late == '/')
if (pre == '^' || pre == '*' || pre == '/') return true;
else return false;
if (late == '+' || late == '-')
if (pre == '(') return false;
else return true;
return false;
}
void CalFix() { //后缀表达式计算
for (int i = 0; i < fixStr.length(); i++) {
switch (fixStr[i]) {
case '+':Calculate('+'); break;
case '/':Calculate('/'); break;
case '*':Calculate('*'); break;
case '-':Calculate('-'); break;
case '^':Calculate('^'); break;
case ' ': break;
default:
int a;
a = (int)(fixStr[i] - 48);
MoveIn.push(a);
break;
}
}
cout << MoveIn.top();
}
void Calculate(char np) { //弹出两个栈内数运算后再压进栈
int pre, late;
late = MoveIn.top();
MoveIn.pop();
pre = MoveIn.top();
MoveIn.pop();
switch (np) {
case '+':MoveIn.push(pre + late); break;
case '/':MoveIn.push(pre / late); break;
case '*':MoveIn.push(pre * late); break;
case '-':MoveIn.push(pre - late); break;
case '^':MoveIn.push(pow(pre,late)); break;
default:
break;
}
}